版本比较

旧版本 5

changes.mady.by.user zhongluqiang

保存于

比较

新版本 当前版本

changes.mady.by.user zhongluqiang

保存于

标识

  • 该行被添加。
  • 该行被删除。
  • 格式已经改变。

01背包

题目链接：2. 01背包问题 - AcWing题库

有N件物品和一个容量为V的背包，第i件物品的费用是c[i]，价值是w[i]，求将哪些物品装入背包可使总费用不超过背包的容量，且价值之和最大。

重点：每件物品仅有一件，可以取或不取。

朴素解法

二维DP解法

定义Fdp[i][vj]表示将第i件物品放入一个容量为vj的背包的价值，则其状态转移方程如下：

Fdp[i][vj] = max{Fdp[i-1][vj], Fdp[i-1][vj-c[i]] + w[i]}

上面的这个方程的含义如下：

  1. 将第i件物品放入容量为vj的背包的最大价值，只需要考虑第i件物品是否放入背包，有放和不放两种情况。
  2. 如果不放第i件物品，那么总价值就是前i-1件物品放入容量为vj的背包的价值，也就是Fdp[i-1][vj]。
  3. 如果放入第i件物品，那么就价值就是第件物品，那么总价值就是第i件物品的价值w[i]，加上前i-1件物品放入容量为vj-c[i]的背包的价值Fdp[i-1][vj-c[i]]。
  4. 以上两者取最大值，即为第i件物品放入容量为vj的背包的最大价值。

示例代码实现如下：

代码块
#define#include MAXN 1005

int n; // 物品数
int v; // 背包容量<iostream>
using namespace std;

#define MAXN 1005

int c[MAXN]; // 物品费用 
int w[MAXN]; // 物品价值
int fdp[MAXN][MAXN]; // fdp[i][j]，j体积下前i个物品的最大价值表示第i件物品放入容量为j的背包的价值

int knapsack01main() {
    int n, v; // 物品数，背包容量
    cin >> n >> v;
    for(int i = 1; i <= n; i++) { // 下标从1开始
        cin >> c[i] >> w[i];
    }

    // 注意这里隐含设置了取0件物品和背包容量为0时f数组对应的值全为0的情况注意这里隐含设置了取0件物品和背包容量为0时dp数组对应的值全为0的情况
    // for(int i = 0; i <= v; i++) fdp[0][i] = 0;
    // for(int i = 0; i <= n; i++) fdp[i][0] = 0; 

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= v; j++) {
            if(j < c[i]) {   
                // 当前背包容量j装不下第i个物品，则价值等于前i-1个物品 
                fdp[i][j] = fdp[i-1][j];
            } else {
                // 能装，按方程进行决策
                // 注意，当到j恰好能装下全部的前i件物品时，
                // 后续的j可直接设置成f[i][j-1]，因为后续的j表示背包容量已经有冗余了
                fdp[i][j] = max(fdp[i-1][j], fdp[i-1][j - c[i]] + w[i]);
            }
        }
    }

    cout return<< fdp[n][v];
}

优化空间复杂度

根据状态转移方程可知，第i件物品的计算过程只与第i-1件物品有关，由于可以想到使用滚动数组的方式，将空间复杂度降为从二维降至一维。

  1. 定义状态fdp[j]，表示N件物品在背包容量为j下的最优解。
  2. 枚举容量，j必须从V枚举到0，也就是逆序。

  3. 为什么采用逆序，参考以下解释：

    提示

    状态方程：dp[j] = max(dp[j], dp[j - vc[i]] + w[i])

    假如枚举到：i = 3, j = 8, vc[3] = 5, w[3] = 1

    二维：dp[3][8] = max(dp[2][8], dp[2][3] + w[3])   此时的dp[2][8]和dp[2][3]都是上一轮的状态值

    一维：dp[8] = max(dp[8], dp[3] + w[3])      我们要保证我们要保证dp[8]和dp[3]都是上一轮的状态值

    按照逆序的顺序，一维dp数组的更新顺序为：dp[8], dp[7], dp[6], ... , dp[3]

    也就是说，在本轮更新的值，不会影响本轮中其他未更新的值！较小的index对应的状态是上一轮的状态值！

    如果按照顺序进行更新，dp[3] = max(dp[3], dp[0] + w[0])，对dp[3]的状态进行了更新，那么在更新dp[8]时，用到的dp[3]就不是上一轮的状态了，不满足动态规划的要求。

    作者：polaris
    链接：https://www.acwing.com/solution/content/3982/
    来源：AcWing
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    简单来说，如果从小到大更新j，则先更新dp[3]，后面再更新dp[8]时会用到已经更新过的dp[3]，而不是上一轮的dp[3]，而如果按从大到小更新j，则先更新dp[8]，此时用到的dp[3]还是上一轮的dp[3]。

    由于dp[j]的更新依赖于上一轮的dp[j-c[i]]，这就需要保证在更新dp[j]时，所有比j小的dp都是未更新过的。

示例代码：

代码块
#define#include MAXN 1005

int n; // 物品数
int v; // 背包容量<iostream>
using namespace std;

#define MAXN 1005

int c[MAXN]; // 物品费用 
int w[MAXN]; // 物品价值
int fdp[MAXN]; // fdp[j]，j体积下前N个物品的最大价值表示N个物品在容量j下的最优解

int knapsack01main() {
    int n, v;
    cin >> n >> v;
    for(int i = 1; i <= n; i++) { // 下标从1开始
        cin >> c[i] >> w[i];
    }

    for(int i = 1; i <= n; i++) {
        for(int j = v; j >= 0; j--) {
            if(j < c[i]) {
                fdp[j] = fdp[j]; // 这里左边的是第i轮的f左边的dp[j]，右边的是第i-1轮的f是第i轮的值，右边的dp[j]是第i-1轮的值
            } else {
                fdp[j] = max(fdp[j], fdp[j - c[i]] + w[i]);
            }
        }
    }
    
    returncout << fdp[v];
}

以上代码的循环部分可进一步简化：

代码块
#include <iostream>
using namespace std;

#define MAXN 1005

int c[MAXN]; // 物品费用
int w[MAXN]; // 物品价值
int dp[MAXN]; // dp[j]表示N个物品在容量j下的最优解

int main() {
    int n, v;
    cin >> n >> v;
    for(int i = 1; i <= n; i++) {
        cin >> c[i] >> w[i];
    }

    for(int i = 1; i <= n; i++) {
        for(int j = v; j >= c[i]; j--) {
           f dp[j] = max(fdp[j], fdp[j - c[i]] + w[i]); // 左边的dp[j]是第i轮的值，右边的dp[j-c[i]]是第i-1轮的值
        }
    }
    
    cout << dp[v];
}

优化输入

可以转化成在线处理输入的方式，而不必开两个数组来保存可以使用在线处理输入的方式，边输入边计算，而不必开两个数组来保存c和w，如下：

代码块
#include <iostream>
using namespace std;

#define MAXN 1005

int fdp[MAXN];

int main() {
    int n, v;
    cin >> n >> v;
    
    for(int i = 1; i <= n; i++) {
        int c, w;
        cin >> c >> w;
        for(int j = v; j >= c; j--) {
            fdp[j] = max(fdp[j], fdp[j - c] + w);
        }
    }
    
    cout << fdp[v];
}











目录