01背包问题-526互联

题目链接

解题思路

处理输入
输入 n, m，v[i], w[i] 等信息
算法核心
动态规划的思想是通过计算当前的值，这个值能被后来使用，最后得到解
- 属性：求最大价值
- 状态表示：只考虑前 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 的最大价值，正好就是题目的要求
代码

#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;
}

注意事项
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;
}