背包问题（一）

一.01背包有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi价值是 wi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。0N,V≤100000vi,wi≤1000一.详细分析“01背包”动态规划思路1.问题本质你有一个容量有限的背包和一堆物品。每个物品有自己的体积和价值。你的目标是在不超过背包容量的前提下选择一些物品装入背包使得这些物品的总价值最大。关键在于“0-1”每个物品只有两种命运要么被选中 (1)要么不被选中 (0)。不能只装入一个物品的一部分。2.动态规划DP的核心思想动态规划的精髓在于将复杂问题分解为更小的、重叠的子问题并通过存储子问题的解记忆化来避免重复计算最终构建出原问题的解。对于背包问题我们定义的状态子问题是dp[i][j]表示一个状态只考虑前i个物品在背包容量为j的情况下可以获得的最大价值。i的范围是0到N物品编号从1开始i0表示不考虑任何物品。j的范围是0到V背包容量。我们的最终目标就是求出dp[N][V]的值。3.状态转移方程最关键的一步1.不选第i个物品如果我们决定不拿这个物品那么情况就变得非常简单。此时的最大价值就等于只考虑前i-1个物品且背包容量仍然为j时的最大价值。也就是dp[i][j] dp[i-1][j]。2.选择第i个物品如果我们决定拿这个物品那么首先有一个前提条件背包的剩余容量必须至少能装下这个物品即j v[i]。如果我们拿了这个物品我们会获得它的价值w[i]但同时也会消耗掉v[i]的背包容量。那么剩下的背包容量就是j - v[i]。在这些剩余的容量里我们依然要做出最优决策。“只考虑前i-1个物品背包容量为j - v[i]时的最大价值”就是我们在剩余容量上能获得的最大价值即dp[i-1][j - v[i]]。所以选择第i个物品带来的总价值是w[i] dp[i-1][j - v[i]]。结论我们的目标是最大化价值。因此对于每一种状态(i, j)我们都在上述两种选择中挑一个更好的价值更大的。综合起来就是如果 j v[i] (当前背包容量装不下第i个物品)dp[i][j] dp[i-1][j] // 只能不选否则 (可以装下进行决策)dp[i][j] max( dp[i-1][j], // 不选第i个物品w[i] dp[i-1][j - v[i]] // 选择第i个物品)4.初始化我们需要一个初始状态来开始整个递推过程。dp[0][0..V]考虑前0个物品也就是没有任何物品可选。那么无论背包容量有多大能获得的最大价值都是0。同样dp[0..N][0]背包容量为0。那么无论有多少物品你都装不下任何东西最大价值也是0。在实际代码中我们通常会创建一个大小为(N1) x (V1)的二维数组并将第一行 (i0) 和第一列 (j0) 全部初始化为0。5.计算顺序与填表有了初始状态和状态转移方程我们就可以想填表一样计算出所有状态的值。1.外层循环i从1到N逐个考虑每个物品。2.内层循环j从0到V逐个考虑每种可能的背包容量。3.对于每一个(i, j)根据上面的状态转移方程利用之前已经计算好的dp[i-1][...]的值来计算dp[i][j]。最终表格最右下角的值dp[N][V]就是我们要求的答案。6.空间优化滚动数组或一维数组仔细观察状态转移方程你会发现在计算dp[i]这一行的所有状态时只依赖于上一行dp[i-1]的数据而更早的数据就不再需要了。这意味着我们并不需要存储整个N x V的二维数组。我们可以使用一个一维数组dp[0..V]来滚动更新。这个一维数组dp[j]在计算过程中实际表示的是上一轮i-1的结果即dp[i-1][j]。当我们计算新的一轮i时我们想要用上一轮的数据来覆盖它得到dp[i][j]。但是这里有一个关键点内层循环j必须从大到小从V到0进行遍历。为什么因为状态转移方程需要的是dp[i-1][j - v[i]]也就是上一轮、更小容量的状态。如果我们从小到大遍历j那么当我们计算dp[j]时dp[j - v[i]]可能已经在本轮被更新过了变成了dp[i][j - v[i]]这就污染了我们需要使用的“上一轮”的数据。而从大到小遍历可以保证我们使用的dp[j - v[i]]仍然是上一轮的结果。优化后的状态转移一维数组for (int i 1; i N; i) { for (int j V; j v[i]; j--) { // 逆序更新容量 dp[j] max(dp[j], w[i] dp[j - v[i]]); } // j v[i] 时dp[j] 保留上一轮的值 }二.代码展示二维数组#include iostream #include algorithm using namespace std; const int MAX_N 1010; const int MAX_V 1010; int main() { int N, V; cin N V; // 物品数组下标从1开始使用 int v[MAX_N] {0}; // 体积 int w[MAX_N] {0}; // 价值 // 读取物品信息 for (int i 1; i N; i) { cin v[i] w[i]; } // DP数组dp[i][j]表示考虑前i个物品背包容量为j时的最大价值 int dp[MAX_N][MAX_V] {0}; // 动态规划过程 for (int i 1; i N; i) { // 遍历每个物品 for (int j 0; j V; j) { // 遍历每种容量 // 默认不选第i个物品 dp[i][j] dp[i - 1][j]; // 如果当前容量可以装下第i个物品考虑选择它 if (j v[i]) { dp[i][j] max(dp[i][j], dp[i - 1][j - v[i]] w[i]); } } } // 输出结果考虑前N个物品容量为V时的最大价值 cout dp[N][V] endl; return 0; }一维数组#include iostream #include algorithm #include vector using namespace std; int main() { int n, v; cin n v; vectorint dp(v 1, 0); for (int i 0; i n; i) { int vi, wi; cin vi wi; for (int j v; j vi; --j) { dp[j] max(dp[j], dp[j - vi] wi); } } cout dp[v]; }二.完全背包有 N 种物品和一个容量是 V 的背包每种物品都有无限件可用。第 i 种物品的体积是 vi价值是 wi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。0N,V≤100000vi,wi≤1000一.问题本质与0-1背包不同完全背包中每种物品都有无限件可用。这意味着对于每种物品你可以选择拿0件、1件、2件...直到背包容量装不下为止。你的目标依然是在不超过背包容量的前提下选择物品数量不限使得总价值最大。二.动态规划思路依然使用动态规划定义的状态是dp[i][j]表示考虑前i种物品在背包容量为j的情况下可以获得的最大价值。1.状态转移方程分析对于第i种物品我们现在有多种选择可以拿0件、1件、2件...k件只要不超过背包容量。因此状态转移方程需要遍历所有可能的数量dp[i][j] max{dp[i-1][j], // 不拿第i种物品dp[i-1][j - v[i]] w[i], // 拿1件第i种物品dp[i-1][j - 2*v[i]] 2*w[i], // 拿2件第i种物品...dp[i-1][j - k*v[i]] k*w[i] // 拿k件第i种物品}其中 k 满足k * v[i] j2.优化状态转移方程上面的方程需要遍历k时间复杂度较高O(NVV)。可以通过数学变换来优化观察dp[i][j]和dp[i][j - v[i]]的关系dp[i][j] max( dp[i-1][j], dp[i-1][j-v[i]] w[i], dp[i-1][j-2v[i]] 2w[i], ... )dp[i][j - v[i]] max( dp[i-1][j-v[i]], dp[i-1][j-2v[i]] w[i], dp[i-1][j-3v[i]] 2w[i], ... )可以发现dp[i][j] max( dp[i-1][j], dp[i][j - v[i]] w[i] )这个优化后的方程极其重要它的含义是要么不选第i种物品dp[i-1][j]要么至少选一件第i种物品dp[i][j - v[i]] w[i]注意这里第二项是dp[i][j - v[i]]而不是dp[i-1][j - v[i]]这是因为我们允许重复选择同一物品。3.最终的状态转移方程如果 j v[i]:dp[i][j] dp[i-1][j]否则:dp[i][j] max( dp[i-1][j], dp[i][j - v[i]] w[i] )4.初始化与0-1背包相同dp[0][0..V] 0没有物品可选dp[0..N][0] 0没有容量可用5.空间优化一维数组同样可以优化空间使用一维数组dp[j]。但注意这里内层循环需要从小到大遍历为什么因为状态转移方程是dp[i][j] max(dp[i-1][j], dp[i][j - v[i]] w[i])我们需要的是本轮的dp[i][j - v[i]]所以应该先计算小的j再计算大的j。优化后的代码结构for (int i 1; i N; i) { for (int j v[i]; j V; j) { // 从小到大遍历 dp[j] max(dp[j], dp[j - v[i]] w[i]); } }三.代码展示二维数组#include bits/stdc.h using namespace std; int main() { int n, v; cin n v; vectorint vi(n 1, 0); vectorint wi(n 1, 0); vectorvectorint dp(n 1, vectorint(v 1, 0)); for (int i 1; i n; i) cin vi[i] wi[i]; for (int i 1; i n; i) { for (int j 0; j v; j) { if (j vi[i]) dp[i][j] dp[i - 1][j]; else { dp[i][j] max(dp[i - 1][j], dp[i][j - vi[i]] wi[i]); } } } cout dp[n][v] endl; }一维数组#include bits/stdc.h using namespace std; int main() { int n, v; cin n v; vectorint vi(n 1, 0); vectorint wi(n 1, 0); vectorint dp(v 1, 0); for (int i 1; i n; i) cin vi[i] wi[i]; for (int i 1; i n; i) { for (int j vi[i]; j v; j) { dp[j] max(dp[j], dp[j - vi[i]] wi[i]); } } cout dp[v] endl; }