多重背包问题 I有 NN 种物品和一个容量是 VV 的背包。第 ii 种物品最多有 sisi 件每件体积是 vivi价值是 wiwi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数NVNV用空格隔开分别表示物品种数和背包容积。接下来有 NN 行每行三个整数 vi,wi,sivi,wi,si用空格隔开分别表示第 ii 种物品的体积、价值和数量。输出格式输出一个整数表示最大价值。数据范围0N,V≤1000N,V≤1000vi,wi,si≤100一、问题本质多重背包问题是介于0-1背包和完全背包之间的问题0-1背包每种物品最多1件选或不选完全背包每种物品无限件多重背包每种物品有有限件具体数量为 si 件二、动态规划思路依然定义状态dp[i][j]表示考虑前i种物品在背包容量为j的情况下可以获得的最大价值。1、状态转移方程分析对于第i种物品现在有多种选择可以拿0件、1件、2件...最多拿min(si, j/vi)件受限于物品数量和背包容量。因此状态转移方程为dp[i][j] max( dp[i-1][j], # 不拿第i种物品 dp[i-1][j - 1*vi] 1*wi, # 拿1件第i种物品 dp[i-1][j - 2*vi] 2*wi, # 拿2件第i种物品 ..., dp[i-1][j - k*vi] k*wi # 拿k件第i种物品 ) # 其中 k min(si, j // vi)2、直接实现三重循环最直接的方法是使用三重循环for (int i 1; i n; i) { for (int j 0; j V; j) { dp[i][j] dp[i-1][j]; // 不选 for (int k 1; k s[i] k * v[i] j; k) { dp[i][j] max(dp[i][j], dp[i-1][j - k*v[i]] k*w[i]); } } }3、时间复杂度这种方法的时间复杂度是 O(NVS)在给定数据范围N,V,S ≤ 100下最大计算量为 100×100×100 1,000,000是可以接受的。三、优化方法二进制优化方法1、为什么需要二进制优化在多重背包的直接解法中我们有三重循环for (i: 物品) for (j: 容量) for (k: 数量) // 遍历0到s[i]件时间复杂度为 O(NVS)。当 S 很大时比如 si 1000计算量会很大。二进制优化可以将时间复杂度降为 O(NVlogS)大大提高了效率。2、二进制优化的核心思想将多重背包问题转化为0-1背包问题但不是简单地将每个物品拆分成 s 个相同的物品而是通过二进制拆分来减少物品数量。3、二进制拆分的原理任何一个正整数都可以用2的幂次方的和来表示13 1 2 4 610 1 2 4 37 1 2 4关键洞察用这些二进制拆分出来的数可以通过组合表示出 0 到原数之间的任何整数。4、具体拆分方法对于数量为 s 的物品我们将其拆分为2⁰, 2¹, 2², ..., 2ᵏ, 剩余部分其中 k 是满足 2⁰ 2¹ ... 2ᵏ ≤ s 的最大整数剩余部分为s - (2ᵏ⁺¹ - 1)。示例s 132⁰ 1, 2¹ 2, 2² 4, 2³ 8 (但1247 138715 13所以取到2²)剩余部分13 - (124) 6拆分结果1, 2, 4, 6用 1, 2, 4, 6 可以组合出 0-13 的任何数字0 不选1 12 23 124 45 146 67 168 269 12610 4611 14612 24613 1246四、二进制优化实现步骤1. 物品拆分对于每个物品 (v, w, s)//此处代码只拆分一个物品拆分n个物品加个for循环 vectorpairint, int new_items; // 存储拆分后的物品 (体积, 价值) for (int k 1; k s; k * 2) { new_items.push_back({k * v, k * w}); s - k; } if (s 0) { new_items.push_back({s * v, s * w}); }2. 转化为0-1背包现在我们得到了一个新的物品列表每个物品只能选一次0-1背包问题。3. 用0-1背包的方法求解// 初始化dp数组一维数组空间优化 vectorint dp(V 1, 0); // 0-1背包求解 for (auto item : new_items) { for (int j V; j item.first; j--) { dp[j] max(dp[j], dp[j - item.first] item.second); } }// 初始化dp数组二维数组更易理解 vectorvectorint dp(M 1, vectorint(V 1, 0)); for (int i 1; i M; i) { for (int j 0; j V; j) { dp[i][j] dp[i-1][j]; if (j v_i) { dp[i][j] max(dp[i][j], dp[i-1][j - v_i] w_i); } } }4、时间复杂度分析原始方法O(NVS)二进制优化O(NVlogS)每个物品最多被拆分成 log₂S 个新物品所以总物品数量从NS降为NlogS。5、空间复杂度分析二维数组空间复杂度O(N ×V)需要存储 (n1) × (V1) 个整数对于 n1000, V1000需要约 1,000,000 个整数约4MB内存对于 n10000, V10000需要约 100,000,000 个整数约400MB内存一维数组空间复杂度O(V)只需要存储 (V1) 个整数对于 V1000需要 1001 个整数约4KB内存对于 V10000需要 10001 个整数约40KB内存6、为什么这样优化有效1、完备性二进制拆分可以表示0-s的任何数量2、独立性每个拆分后的物品只能选一次符合0-1背包3、效率物品数量从s降到logs大大减少计算量五、完整代码三重循环代码#include iostream #include vector #include algorithm using namespace std; int main() { int N, V; cin N V; // 定义数组存储物品信息下标从1开始 vectorint v(N 1); // 物品体积 vectorint w(N 1); // 物品价值 vectorint s(N 1); // 物品数量限制 // 读取输入数据 for (int i 1; i N; i) { cin v[i] w[i] s[i]; } /** * 二维DP数组 * dp[i][j] 表示考虑前i种物品在背包容量为j的情况下能获得的最大价值 * * 初始化全部为0 * - dp[0][j]: 不考虑任何物品价值为0 * - dp[i][0]: 背包容量为0价值为0 */ vectorvectorint dp(N 1, vectorint(V 1, 0)); /** * 三重循环动态规划 * 第一重遍历物品种类 i (从1到N) * 第二重遍历背包容量 j (从0到V) * 第三重遍历当前物品可选数量 k (从0到min(s[i], j/v[i])) */ for (int i 1; i N; i) { for (int j 0; j V; j) { // 首先不考虑选择第i种物品的情况即k0 dp[i][j] dp[i - 1][j]; // 然后考虑选择第i种物品的k件k从1到最大可选数量 for (int k 1; k s[i]; k) { // 计算选择k件第i种物品所需的容量 int volume_needed k * v[i]; // 如果当前容量不足以装下k件物品直接跳出循环 // 因为k继续增大只会需要更多容量更不可能装下 if (j volume_needed) { break; } /** * 状态转移 * 如果选择k件第i种物品 * - 消耗 k * v[i] 的容量 * - 获得 k * w[i] 的价值 * - 剩余容量 j - k*v[i] 用于装前i-1种物品 * * 取最大值不选 vs 选k件 */ int value_if_choose dp[i - 1][j - volume_needed] k * w[i]; dp[i][j] max(dp[i][j], value_if_choose); } } } // 输出结果考虑所有N种物品背包容量为V时的最大价值 cout dp[N][V] endl; return 0; }二进制优化代码用一维数组#include iostream #include vector using namespace std; int main() { int N, V; cin N V; vectorpairint, int items; // 存储拆分后的物品 (v, w) // 二进制拆分 for (int i 0; i N; i) { int v, w, s; cin v w s; for (int k 1; k s; k * 2) { items.push_back({k * v, k * w}); s - k; } if (s 0) { items.push_back({s * v, s * w}); } } // 0-1背包求解 vectorint dp(V 1, 0); for (auto item : items) { for (int j V; j item.first; j--) { dp[j] max(dp[j], dp[j - item.first] item.second); } } cout dp[V] endl; return 0; }用二维数组#include iostream #include vector #include algorithm using namespace std; int main() { int N, V; cin N V; // 存储二进制拆分后的物品 (体积, 价值) vectorpairint, int new_items; // 二进制拆分过程 for (int i 0; i N; i) { int v, w, s; cin v w s; // 使用二进制拆分 for (int k 1; k s; k * 2) { new_items.push_back({k * v, k * w}); s - k; } // 处理剩余部分 if (s 0) { new_items.push_back({s * v, s * w}); } } int M new_items.size(); // 拆分后的物品总数 /** * 二维DP数组 * dp[i][j] 表示考虑前i个拆分后的物品背包容量为j时的最大价值 * 维度 (M1) x (V1) */ vectorvectorint dp(M 1, vectorint(V 1, 0)); /** * 动态规划过程 - 0-1背包 * 第一重遍历拆分后的物品 (从1到M) * 第二重遍历背包容量 (从0到V) */ for (int i 1; i M; i) { // 获取当前物品的体积和价值 int current_v new_items[i - 1].first; int current_w new_items[i - 1].second; for (int j 0; j V; j) { // 默认情况不选当前物品 dp[i][j] dp[i - 1][j]; // 如果当前容量可以装下这个物品考虑选择它 if (j current_v) { dp[i][j] max(dp[i][j], dp[i - 1][j - current_v] current_w); } } } // 输出结果考虑所有拆分后的物品背包容量为V时的最大价值 cout dp[M][V] endl; return 0; }多重背包问题II有 NN 种物品和一个容量是 VV 的背包。第 ii 种物品最多有 sisi 件每件体积是 vivi价值是 wiwi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数NVNV用空格隔开分别表示物品种数和背包容积。接下来有 NN 行每行三个整数 vi,wi,sivi,wi,si用空格隔开分别表示第 ii 种物品的体积、价值和数量。输入格式输出一个整数表示最大价值。数据范围0N≤10000N≤10000V≤20000V≤20000vi,wi,si≤20000vi,wi,si≤2000提示本题考查多重背包的二进制优化方法。相信你一定已经看出来多重背包ll其实就是上述的多重背包l 的二进制优化因为多重背包ll的数据比背包l的数据大得多所以必须使用二进制优化详解如上此处只附上代码。完整的代码#include iostream #include vector using namespace std; int main() { int N, V; cin N V; vectorpairint, int items; // 存储拆分后的物品 (v, w) // 二进制拆分 for (int i 0; i N; i) { int v, w, s; cin v w s; for (int k 1; k s; k * 2) { items.push_back({k * v, k * w}); s - k; } if (s 0) { items.push_back({s * v, s * w}); } } // 0-1背包求解 vectorint dp(V 1, 0); for (auto item : items) { for (int j V; j item.first; j--) { dp[j] max(dp[j], dp[j - item.first] item.second); } } cout dp[V] endl; return 0; }
背包问题（二）
多重背包问题 I有 NN 种物品和一个容量是 VV 的背包。第 ii 种物品最多有 sisi 件每件体积是 vivi价值是 wiwi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数NVNV用空格隔开分别表示物品种数和背包容积。接下来有 NN 行每行三个整数 vi,wi,sivi,wi,si用空格隔开分别表示第 ii 种物品的体积、价值和数量。输出格式输出一个整数表示最大价值。数据范围0N,V≤1000N,V≤1000vi,wi,si≤100一、问题本质多重背包问题是介于0-1背包和完全背包之间的问题0-1背包每种物品最多1件选或不选完全背包每种物品无限件多重背包每种物品有有限件具体数量为 si 件二、动态规划思路依然定义状态dp[i][j]表示考虑前i种物品在背包容量为j的情况下可以获得的最大价值。1、状态转移方程分析对于第i种物品现在有多种选择可以拿0件、1件、2件...最多拿min(si, j/vi)件受限于物品数量和背包容量。因此状态转移方程为dp[i][j] max( dp[i-1][j], # 不拿第i种物品 dp[i-1][j - 1*vi] 1*wi, # 拿1件第i种物品 dp[i-1][j - 2*vi] 2*wi, # 拿2件第i种物品 ..., dp[i-1][j - k*vi] k*wi # 拿k件第i种物品 ) # 其中 k min(si, j // vi)2、直接实现三重循环最直接的方法是使用三重循环for (int i 1; i n; i) { for (int j 0; j V; j) { dp[i][j] dp[i-1][j]; // 不选 for (int k 1; k s[i] k * v[i] j; k) { dp[i][j] max(dp[i][j], dp[i-1][j - k*v[i]] k*w[i]); } } }3、时间复杂度这种方法的时间复杂度是 O(NVS)在给定数据范围N,V,S ≤ 100下最大计算量为 100×100×100 1,000,000是可以接受的。三、优化方法二进制优化方法1、为什么需要二进制优化在多重背包的直接解法中我们有三重循环for (i: 物品) for (j: 容量) for (k: 数量) // 遍历0到s[i]件时间复杂度为 O(NVS)。当 S 很大时比如 si 1000计算量会很大。二进制优化可以将时间复杂度降为 O(NVlogS)大大提高了效率。2、二进制优化的核心思想将多重背包问题转化为0-1背包问题但不是简单地将每个物品拆分成 s 个相同的物品而是通过二进制拆分来减少物品数量。3、二进制拆分的原理任何一个正整数都可以用2的幂次方的和来表示13 1 2 4 610 1 2 4 37 1 2 4关键洞察用这些二进制拆分出来的数可以通过组合表示出 0 到原数之间的任何整数。4、具体拆分方法对于数量为 s 的物品我们将其拆分为2⁰, 2¹, 2², ..., 2ᵏ, 剩余部分其中 k 是满足 2⁰ 2¹ ... 2ᵏ ≤ s 的最大整数剩余部分为s - (2ᵏ⁺¹ - 1)。示例s 132⁰ 1, 2¹ 2, 2² 4, 2³ 8 (但1247 138715 13所以取到2²)剩余部分13 - (124) 6拆分结果1, 2, 4, 6用 1, 2, 4, 6 可以组合出 0-13 的任何数字0 不选1 12 23 124 45 146 67 168 269 12610 4611 14612 24613 1246四、二进制优化实现步骤1. 物品拆分对于每个物品 (v, w, s)//此处代码只拆分一个物品拆分n个物品加个for循环 vectorpairint, int new_items; // 存储拆分后的物品 (体积, 价值) for (int k 1; k s; k * 2) { new_items.push_back({k * v, k * w}); s - k; } if (s 0) { new_items.push_back({s * v, s * w}); }2. 转化为0-1背包现在我们得到了一个新的物品列表每个物品只能选一次0-1背包问题。3. 用0-1背包的方法求解// 初始化dp数组一维数组空间优化 vectorint dp(V 1, 0); // 0-1背包求解 for (auto item : new_items) { for (int j V; j item.first; j--) { dp[j] max(dp[j], dp[j - item.first] item.second); } }// 初始化dp数组二维数组更易理解 vectorvectorint dp(M 1, vectorint(V 1, 0)); for (int i 1; i M; i) { for (int j 0; j V; j) { dp[i][j] dp[i-1][j]; if (j v_i) { dp[i][j] max(dp[i][j], dp[i-1][j - v_i] w_i); } } }4、时间复杂度分析原始方法O(NVS)二进制优化O(NVlogS)每个物品最多被拆分成 log₂S 个新物品所以总物品数量从NS降为NlogS。5、空间复杂度分析二维数组空间复杂度O(N ×V)需要存储 (n1) × (V1) 个整数对于 n1000, V1000需要约 1,000,000 个整数约4MB内存对于 n10000, V10000需要约 100,000,000 个整数约400MB内存一维数组空间复杂度O(V)只需要存储 (V1) 个整数对于 V1000需要 1001 个整数约4KB内存对于 V10000需要 10001 个整数约40KB内存6、为什么这样优化有效1、完备性二进制拆分可以表示0-s的任何数量2、独立性每个拆分后的物品只能选一次符合0-1背包3、效率物品数量从s降到logs大大减少计算量五、完整代码三重循环代码#include iostream #include vector #include algorithm using namespace std; int main() { int N, V; cin N V; // 定义数组存储物品信息下标从1开始 vectorint v(N 1); // 物品体积 vectorint w(N 1); // 物品价值 vectorint s(N 1); // 物品数量限制 // 读取输入数据 for (int i 1; i N; i) { cin v[i] w[i] s[i]; } /** * 二维DP数组 * dp[i][j] 表示考虑前i种物品在背包容量为j的情况下能获得的最大价值 * * 初始化全部为0 * - dp[0][j]: 不考虑任何物品价值为0 * - dp[i][0]: 背包容量为0价值为0 */ vectorvectorint dp(N 1, vectorint(V 1, 0)); /** * 三重循环动态规划 * 第一重遍历物品种类 i (从1到N) * 第二重遍历背包容量 j (从0到V) * 第三重遍历当前物品可选数量 k (从0到min(s[i], j/v[i])) */ for (int i 1; i N; i) { for (int j 0; j V; j) { // 首先不考虑选择第i种物品的情况即k0 dp[i][j] dp[i - 1][j]; // 然后考虑选择第i种物品的k件k从1到最大可选数量 for (int k 1; k s[i]; k) { // 计算选择k件第i种物品所需的容量 int volume_needed k * v[i]; // 如果当前容量不足以装下k件物品直接跳出循环 // 因为k继续增大只会需要更多容量更不可能装下 if (j volume_needed) { break; } /** * 状态转移 * 如果选择k件第i种物品 * - 消耗 k * v[i] 的容量 * - 获得 k * w[i] 的价值 * - 剩余容量 j - k*v[i] 用于装前i-1种物品 * * 取最大值不选 vs 选k件 */ int value_if_choose dp[i - 1][j - volume_needed] k * w[i]; dp[i][j] max(dp[i][j], value_if_choose); } } } // 输出结果考虑所有N种物品背包容量为V时的最大价值 cout dp[N][V] endl; return 0; }二进制优化代码用一维数组#include iostream #include vector using namespace std; int main() { int N, V; cin N V; vectorpairint, int items; // 存储拆分后的物品 (v, w) // 二进制拆分 for (int i 0; i N; i) { int v, w, s; cin v w s; for (int k 1; k s; k * 2) { items.push_back({k * v, k * w}); s - k; } if (s 0) { items.push_back({s * v, s * w}); } } // 0-1背包求解 vectorint dp(V 1, 0); for (auto item : items) { for (int j V; j item.first; j--) { dp[j] max(dp[j], dp[j - item.first] item.second); } } cout dp[V] endl; return 0; }用二维数组#include iostream #include vector #include algorithm using namespace std; int main() { int N, V; cin N V; // 存储二进制拆分后的物品 (体积, 价值) vectorpairint, int new_items; // 二进制拆分过程 for (int i 0; i N; i) { int v, w, s; cin v w s; // 使用二进制拆分 for (int k 1; k s; k * 2) { new_items.push_back({k * v, k * w}); s - k; } // 处理剩余部分 if (s 0) { new_items.push_back({s * v, s * w}); } } int M new_items.size(); // 拆分后的物品总数 /** * 二维DP数组 * dp[i][j] 表示考虑前i个拆分后的物品背包容量为j时的最大价值 * 维度 (M1) x (V1) */ vectorvectorint dp(M 1, vectorint(V 1, 0)); /** * 动态规划过程 - 0-1背包 * 第一重遍历拆分后的物品 (从1到M) * 第二重遍历背包容量 (从0到V) */ for (int i 1; i M; i) { // 获取当前物品的体积和价值 int current_v new_items[i - 1].first; int current_w new_items[i - 1].second; for (int j 0; j V; j) { // 默认情况不选当前物品 dp[i][j] dp[i - 1][j]; // 如果当前容量可以装下这个物品考虑选择它 if (j current_v) { dp[i][j] max(dp[i][j], dp[i - 1][j - current_v] current_w); } } } // 输出结果考虑所有拆分后的物品背包容量为V时的最大价值 cout dp[M][V] endl; return 0; }多重背包问题II有 NN 种物品和一个容量是 VV 的背包。第 ii 种物品最多有 sisi 件每件体积是 vivi价值是 wiwi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。输入格式第一行两个整数NVNV用空格隔开分别表示物品种数和背包容积。接下来有 NN 行每行三个整数 vi,wi,sivi,wi,si用空格隔开分别表示第 ii 种物品的体积、价值和数量。输入格式输出一个整数表示最大价值。数据范围0N≤10000N≤10000V≤20000V≤20000vi,wi,si≤20000vi,wi,si≤2000提示本题考查多重背包的二进制优化方法。相信你一定已经看出来多重背包ll其实就是上述的多重背包l 的二进制优化因为多重背包ll的数据比背包l的数据大得多所以必须使用二进制优化详解如上此处只附上代码。完整的代码#include iostream #include vector using namespace std; int main() { int N, V; cin N V; vectorpairint, int items; // 存储拆分后的物品 (v, w) // 二进制拆分 for (int i 0; i N; i) { int v, w, s; cin v w s; for (int k 1; k s; k * 2) { items.push_back({k * v, k * w}); s - k; } if (s 0) { items.push_back({s * v, s * w}); } } // 0-1背包求解 vectorint dp(V 1, 0); for (auto item : items) { for (int j V; j item.first; j--) { dp[j] max(dp[j], dp[j - item.first] item.second); } } cout dp[V] endl; return 0; }
