acwing 3 完全背包问题

题面

题解

完全背包问题 ：每个物品可以拿无限次 （只能用DP求最优解，不能用贪心）

为什么不能用贪心：我们每次将性价比最高的（价值/体积 最大）放入背包，直到放不下为止，然后继续放性价比次高的 ，这样看似正确，但是贪心只考虑了局部最优解，但是没有办法保证背包的剩余容量最小，无法保证背包的利用价值最大，举个例子，有两种物品 v1=5 w1=21 ,v2=3 w2=12 背包的体积是6 ，用贪心的话先选（21/5=4.2）性价比高的，但是背包容量剩余1，最终价值是21，但是如果选择2的话，可以选两个，最终价值是24

DP集合划分

代码

朴素做法，n3 容易理解但是复杂度太高，会超时

#include<bits/stdc++.h>

using namespace std;
const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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 = 0; j <= m; j++) {
            for (int k = 0; k * v[i] <= j; k++) {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }

    cout << f[n][m] << endl;

    return 0;
}
           

优化（n2）

我们将k去掉改成枚举，选取最大值，对于这两项我们可以发现，由 f[i][j-v]变成f[i][j]最大值只是多了一个 w，与 k 并无关系，那么我们就可以用 f[i][j-v[i]] 来更新状态方程式，改为 f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])

#include<bits/stdc++.h>

using namespace std;
const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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 = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) {
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
            }
        }
    }

    cout << f[n][m] << endl;

    return 0;
}
           

一维优化

看到上面的代码是否有熟悉的感觉，其实和01背包已经很像了，只是01背包f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) 是从i-1层转移的，而完全背包是从第i层转移过来的

所以也没有01背包的问题（01背包是从i-1层更新，所以要倒序保证前一个不被覆盖），而完全背包只用到了i层，所以直接删掉一维就好

#include<bits/stdc++.h>

using namespace std;
const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

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++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << endl;

    return 0;
}