背包问题 模板

01 背包问题

一维数组（滚动数组）模板

for(int i = 1; i <= m; ++i){  //小于等于总个数，从 1 开始
    for(int j = T; j >= 0; --j){  //逆序，从总容量开始递减
        if(j >= good[i].t){  //单个物品体积不超过背包容量 
            dp[j] = max(dp[j], dp[j-good[i].t]+good[i].w);  //减去单个物品体积后的 dp + 这个物品的重量
        }
    }
}
例题

完全背包问题

一维数组（滚动数组）模板

for(int i = 1; i <= m; ++i){  //小于等于总个数，从 1 开始
    for(int j = good[i].t; j <= T; ++j){  //完全背包：顺序 
        dp[j] = max(dp[j], dp[j-good[i].t]+good[i].w);  //减去单个物品体积后的 dp + 这个物品的重量
    }
}
例题

带附件的背包问题

模板（以两个附件为例）

for(int i = 1; i <= m; ++i){  //i <= 可选的物品种类，从1开始 
    for(int j = n; j >= 0; --j){  //j = 总钱数 
        if(j >= good[i][0].v){  //只选主件 
            dp[j] = max(dp[j], dp[j-good[i][0].v]+good[i][0].w);  //不选当前件，选择当前件所以要花费当前物品的费用，再加上总价值 
        }
        if(j >= good[i][0].v+good[i][1].v){  //选主件+附件1 
            dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][1].v] + 
                        good[i][0].w+good[i][1].w); 
        }
        if(j >= good[i][0].v+good[i][2].v){  //选主件+附件2 
            dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][2].v] + 
                        good[i][0].w+good[i][2].w);
        }
        if(j >= good[i][0].v+good[i][1].v+good[i][2].v){  //都选 
            dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][1].v-good[i][2].v]
                        + good[i][0].w+good[i][1].w+good[i][2].w);
        } 
    }
}
例题

多重背包

模板

//完全背包 
void CompletePack(int v, int w, int m){
	for(int i = v; i <= m; ++i){
		dp[i] = maxx(dp[i], dp[i-v]+w);
	}
}

//01背包
void ZeroOnePack(int v, int w, int m){
	for(int i = m; i >= v; --i){
		dp[i] = maxx(dp[i], dp[i-v]+w);
	}
} 

//多重背包
void MultiPack(int v, int w, int m,int c){
	if(v*c >= m){
		CompletePack(v,w,m);	
	}
	else{
		int k = 1;
		while(k < c){
			ZeroOnePack(k*v,k*w,m);
			c -= k;
			k *= 2;
		}
		ZeroOnePack(c*v, c*w, m);
	}
}
例题