01背包问题

题目链接

Acwing 01背包问题

解题思路

1. 处理输入
   输入 n, m，v[i], w[i] 等信息

2. 算法核心
   动态规划的思想是通过计算当前的值，这个值能被后来使用，最后得到解

   • 属性：求最大价值
   • 状态表示：只考虑前 i 件物品时，体积为 j 的最大价值
   • 思路：
     只考虑前 i 件物品时，体积为 j 的最大价值，这个价值可以通过“只考虑前 i - 1 件物品时，体积为 j 的最大价值”这个量给求出来。求的方法是计算选上第 i 件物品和不选上第 i 件物品的最大值。
   • 代码表示：
     s[i][j] = s[i - 1][j];
     if (j >= v[i]) s[i][j] = max(s[i][j], s[i - 1][j - v[i]] + w[i]);
   • 最后取值：根据状态表示来决定，将 n 和 m 代入理解即是：只考虑前 n 件物品时，体积为 m 的最大价值，正好就是题目的要求

3. 代码

#include<iostream>
using namespace std;

const int N = 1010;
int v[N], w[N];
int s[N][N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    s[0][0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s[i][j] = s[i - 1][j];
            if (j >= v[i]) {
                s[i][j] = max(s[i - 1][j], s[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    
    cout << s[n][m] << endl;
    
    return 0;
}

4. 注意事项
   1. 读入的 v[i] 和 w[i] 数组都是从 1 开始
   2. 注意这里因为所有的 s[i] 都被初始化为0，所以才可使用 s[n][m]

01背包问题的优化

因为每次求第 i 次的状态只要求第 i - 1 次的状态，所以我们考虑降低维度，少一个循环。这里直观的考虑是使用滚动数组来解决，但不必要，使用一维的数组就可以解决。

解决方法如下：

• 直接把二维变为一维，在不影响原来代码的逻辑上，更改代码
• 删掉 s[i][j] = s[i - 1][j];
• 将状态转移方程直接改为一维：s[j] = max(s[j], s[j - v[i]] + w[i]);
• 为了不影响逻辑，观察：在计算 s[j] 的时候，因为循环是从小到大的，其实 s[j - v[i]] 已经被计算过了，所以 s[j - v[i]] 已经是第 i 层的结果了，被更新过了。所以解决办法是：把循环从 m 到 0。又由于有if (j >= v[i])这个状态，所以，循环从 m 到 v[i] 即可。
• 考虑最后的结果：如果最初所有s[i]都是0的话，那么结果就是最后一个值；如果不这样，那么就需要 s[0] = 0, 其余的 s[i] 都是 -INF。最后结果还需要求最大值。

代码：

#include<iostream>
using namespace std;

const int N = 1010;
int v[N], w[N];
int s[N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
                s[j] = max(s[j], s[j - v[i]] + w[i]);
        }
    }
    
    cout << s[m] << endl;
    
    return 0;
}