完全背包问题

题目链接

Acwing 完全背包问题

题目思路

完全背包和01背包的区别在于：完全背包中的物品是可以随意数量的。对于一个物品，可以选0个，1个，...，直到选到装不下为止。

• 这里面存在一个转化：
  

• 只从结果来看，完全背包的代码中，唯一区别就是把 f[i - 1][j - v[i]] 改为 f[i][j - v[i]]。

代码：

#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];
    
    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][j], s[i][j - v[i]] + w[i]);
            }
        }
    }
    
    cout << s[n][m] << endl;
    
    return 0;
}

完全背包优化至一维

• 关键：由于完全背包中唯一更改的是 s[i][j - v[i]], 所以这个式子是要求第 i 层的结果，所以要求在计算 s[i][j] 的时候，要把 s[i][j - v[i]] 给算出来，而循环是从小到大的，所以可以直接删掉一层循环。

代码：

#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 = v[i]; j <= m; j++) {
                s[j] = max(s[j], s[j - v[i]] + w[i]);
        }
    }
    
    cout << s[m] << endl;
    
    return 0;
}