题目描述B2173 多重背包代码#includebits/stdc.h using namespace std; int x1[5005],x2[5005],x3[5005]; long long dp[5005][10005]; int main(){ int n,v; cinnv; for(int i1;in;i){ cinx1[i]x2[i]x3[i]; } for(int i1;in;i){ for(int j1;jv;j){ long long zd0; for(int k0;kmin(x3[i],j/x1[i]);k){ long long jzdp[i-1][j-k*x1[i]]k*x2[i]; zdmax(jz,zd); } dp[i][j]zd; } } coutdp[n][v]; return 0; }代码讲解1. 变量定义与含义x1[i]第 i 种物品的体积重量。x2[i]第 i 种物品的价值。x3[i]第 i 种物品的最大可用数量即物品 i 最多可以选多少个。dp[i][j]动态规划数组。表示只考虑前 i 种物品在背包容量为 j 时能获得的最大价值。n物品种类数。v背包总容量。2. 输入部分for(int i1;in;i){ cinx1[i]x2[i]x3[i]; }循环读入 n 种物品的信息每种物品的体积、价值和最大数量。3. 核心动态规划三重循环for(int i1;in;i){ // 枚举物品种类 for(int j1;jv;j){ // 枚举背包容量 long long zd0; // 当前状态的最大价值初始为0 for(int k0;kmin(x3[i],j/x1[i]);k){ // 枚举当前物品选取的数量k long long jzdp[i-1][j-k*x1[i]]k*x2[i]; // 状态转移 zdmax(jz,zd); // 取最大值 } dp[i][j]zd; // 记录最优解 } }状态转移方程dp[i][j] max(dp[i-1][j - k * x1[i]] k * x2[i])其中0 ≤ k ≤ min(x3[i], j / x1[i])解释k表示当前第 i 种物品选取的数量。k的上限有两个约束不能超过该物品的最大数量x3[i]。选取 k 个物品的总体积k * x1[i]不能超过当前背包容量 j即k ≤ j / x1[i]。dp[i-1][j - k * x1[i]]表示不选当前这 k 个物品 i 时用前 i-1 种物品填充剩余容量j - k * x1[i]所能获得的最大价值。 k * x2[i]表示加上当前选的 k 个物品 i 的价值。5. 样例动态规划表n3, V10根据输入样例物品1体积 w13价值 v14数量 c12物品2体积 w24价值 v25数量 c23物品3体积 w32价值 v33数量 c34背包容量 V10。dp[i][j] 表示考虑前 i 种物品、容量为 j 时的最大价值。初始化dp[0][j] 0没有物品可选时价值为0物品1i1jk0k1k2dp[1][j]0-20--03dp[0][3]0dp[0][0]44-44-504-46dp[0][6]0dp[0][3]44dp[0][0]8887-804889dp[0][9]0dp[0][6]44dp[0][3]88810dp[0][10]0dp[0][7]44dp[0][4]888物品2i2基于 dp[1][j] 计算jk0k1k2k3dp[2][j]0-3dp[1][j]---dp[1][j]4dp[1][4]4dp[1][0]55--55dp[1][5]4dp[1][1]55--56dp[1][6]8dp[1][2]55dp[1][-2]无效-87dp[1][7]8dp[1][3]59dp[1][-1]无效-98dp[1][8]8dp[1][4]59dp[1][0]1010-109dp[1][9]8dp[1][5]59dp[1][1]1010dp[1][-3]无效1010dp[1][10]8dp[1][6]513dp[1][2]1010dp[1][-2]无效13物品3i3基于 dp[2][j] 计算jk0k1k2k3k4dp[3][j]0-1dp[2][j]----dp[2][j]2dp[2][2]0dp[2][0]33---33dp[2][3]4dp[2][1]33dp[2][-1]无效--44dp[2][4]5dp[2][2]33dp[2][0]66--65dp[2][5]5dp[2][3]37dp[2][1]66dp[2][-1]无效-76dp[2][6]8dp[2][4]38dp[2][2]66dp[2][0]99-97dp[2][7]9dp[2][5]38dp[2][3]610dp[2][1]99dp[2][-1]无效108dp[2][8]10dp[2][6]311dp[2][4]611dp[2][2]99dp[2][0]1212129dp[2][9]10dp[2][7]312dp[2][5]611dp[2][3]913dp[2][1]12121310dp[2][10]13dp[2][8]313dp[2][6]614dp[2][4]914dp[2][2]121214最终结果dp[3][10] 14与样例输出一致。最优方案为物品1选2件体积6价值8物品3选2件体积4价值6总价值14。4. 输出结果coutdp[n][v];输出考虑所有 n 种物品背包容量为 v 时的最大价值即问题的最终答案。
