【题目来源】https://www.acwing.com/problem/content/8/【题目描述】有 N 件物品和一个容量是 V 的背包背包能承受的最大重量是 M。每件物品只能用一次。体积是 vi重量是 mi价值是 wi。求解将哪些物品装入背包可使物品总体积不超过背包容量总重量不超过背包可承受的最大重量且价值总和最大。输出最大价值。【输入格式】第一行三个整数N,V,M用空格隔开分别表示物品件数、背包容积和背包可承受的最大重量。接下来有 N 行每行三个整数 vi,mi,wi用空格隔开分别表示第 i 件物品的体积、重量和价值。【输出格式】输出一个整数表示最大价值。【数据范围】0N≤10000V,M≤1000vi,mi≤1000wi≤1000【算法分析】● 二维费用背包是背包问题的重要扩展形式其核心特征在于双资源约束。正因如此在求解时我们通常采用二维数组来表示满足双资源约束下的最大价值这便是二维动态规划实现。而根据物品选取规则的不同二维费用背包又可进一步分为二维费用 0/1 背包、二维费用完全背包、二维费用多重背包等典型类型。● 二维费用的背包问题要求对于装入背包的每个物品 i必须同时满足两种不同的限制条件 vol1[i] 与 vol2[i]且每种限制条件的上限分别为 V1 与 V2。若设将物品 i 装入背包可获得的价值为 val[i]请问怎么选择物品可得到最大价值。1下面以二维费用的 0-1 背包问题为例给出一般的二维费用背包问题的解题思路如下令 c[i][j][k] 表示将前 i 种物品装入限制条件1为 j、限制条件2为 k 时可获得的最大价值。根据求解普通 0-1 背包问题的状态转移方程的思路相应可得二维费用的 0-1 背包问题的状态转移方程为c[i][j][k] max(c[i−1][j][k], c[i−1][j−vol1[i]][k−vol2[i]] val[i] )2类似于将普通 0-1 背包问题由二维优化为一维的思路https://blog.csdn.net/hnjzsyjyj/article/details/126071689可以将二维费用的 0-1 背包问题由三维优化为二维从而达到降低算法时间复杂度的目的。优化为二维后的二维费用的 0-1 背包问题的状态转移方程为c[j][k] max(c[j][k], c[j−vol1[i]][k−vol2[i]] val[i])3编写代码时一般采用如下的3重循环for (i1; in; i) // 此行语句也常用 while(n--) 代替其中的n为物品个数 for (jV1; jvol1[i]; j--) for (kV2; kvol2[i]; k--) { c[j][k]max(c[j][k],c[j-vol1[i]][k-vol2[i]]val[i]); }所求最大价值为 c[V1][V2]。【算法代码】#include bits/stdc.h using namespace std; const int N1e35; int f[N][N]; int vol[N],wht[N],val[N]; int main() { int n,V,W; cinnVW; for(int i1; in; i) { cinvol[i]wht[i]val[i]; } for(int i1; in; i) { for(int jV; jvol[i]; j--) { for(int kW; kwht[i]; k--) { f[j][k]max(f[j][k],f[j-vol[i]][k-wht[i]]val[i]); } } } coutf[V][W]endl; return 0; } /* in: 4 5 6 1 2 3 2 4 4 3 4 5 4 5 6 out: 8 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/126229598https://blog.csdn.net/hnjzsyjyj/article/details/126228900
AcWing 8：二维费用 0/1 背包问题 ← 模板题
【题目来源】https://www.acwing.com/problem/content/8/【题目描述】有 N 件物品和一个容量是 V 的背包背包能承受的最大重量是 M。每件物品只能用一次。体积是 vi重量是 mi价值是 wi。求解将哪些物品装入背包可使物品总体积不超过背包容量总重量不超过背包可承受的最大重量且价值总和最大。输出最大价值。【输入格式】第一行三个整数N,V,M用空格隔开分别表示物品件数、背包容积和背包可承受的最大重量。接下来有 N 行每行三个整数 vi,mi,wi用空格隔开分别表示第 i 件物品的体积、重量和价值。【输出格式】输出一个整数表示最大价值。【数据范围】0N≤10000V,M≤1000vi,mi≤1000wi≤1000【算法分析】● 二维费用背包是背包问题的重要扩展形式其核心特征在于双资源约束。正因如此在求解时我们通常采用二维数组来表示满足双资源约束下的最大价值这便是二维动态规划实现。而根据物品选取规则的不同二维费用背包又可进一步分为二维费用 0/1 背包、二维费用完全背包、二维费用多重背包等典型类型。● 二维费用的背包问题要求对于装入背包的每个物品 i必须同时满足两种不同的限制条件 vol1[i] 与 vol2[i]且每种限制条件的上限分别为 V1 与 V2。若设将物品 i 装入背包可获得的价值为 val[i]请问怎么选择物品可得到最大价值。1下面以二维费用的 0-1 背包问题为例给出一般的二维费用背包问题的解题思路如下令 c[i][j][k] 表示将前 i 种物品装入限制条件1为 j、限制条件2为 k 时可获得的最大价值。根据求解普通 0-1 背包问题的状态转移方程的思路相应可得二维费用的 0-1 背包问题的状态转移方程为c[i][j][k] max(c[i−1][j][k], c[i−1][j−vol1[i]][k−vol2[i]] val[i] )2类似于将普通 0-1 背包问题由二维优化为一维的思路https://blog.csdn.net/hnjzsyjyj/article/details/126071689可以将二维费用的 0-1 背包问题由三维优化为二维从而达到降低算法时间复杂度的目的。优化为二维后的二维费用的 0-1 背包问题的状态转移方程为c[j][k] max(c[j][k], c[j−vol1[i]][k−vol2[i]] val[i])3编写代码时一般采用如下的3重循环for (i1; in; i) // 此行语句也常用 while(n--) 代替其中的n为物品个数 for (jV1; jvol1[i]; j--) for (kV2; kvol2[i]; k--) { c[j][k]max(c[j][k],c[j-vol1[i]][k-vol2[i]]val[i]); }所求最大价值为 c[V1][V2]。【算法代码】#include bits/stdc.h using namespace std; const int N1e35; int f[N][N]; int vol[N],wht[N],val[N]; int main() { int n,V,W; cinnVW; for(int i1; in; i) { cinvol[i]wht[i]val[i]; } for(int i1; in; i) { for(int jV; jvol[i]; j--) { for(int kW; kwht[i]; k--) { f[j][k]max(f[j][k],f[j-vol[i]][k-wht[i]]val[i]); } } } coutf[V][W]endl; return 0; } /* in: 4 5 6 1 2 3 2 4 4 3 4 5 4 5 6 out: 8 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/126229598https://blog.csdn.net/hnjzsyjyj/article/details/126228900
