01背包

给出背包容量$V$，$n$件物品，每件物品的体积为$v_i$, 价值为$w_i$，每件物品只能选1次或不选，选取物品总体积不超过$V$的情况下，最大总价值是多少？

定义$f[i,v]$为前$i$件物品放入一个容量为$v$的背包可以获得的最大价值。$f[N,V]$为所求。

$$ f[i,v]=max\{f[i-1, v],f[i-1, v-c_i]+w_i\} $$

// [<https://www.acwing.com/problem/content/2/>](<https://www.acwing.com/problem/content/2/>)
// WA，j<vi时没有转移
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, v;
    cin >> n >> v;
    vector<vector<int>> f(n+1, vector<int>(v+1, 0));
    for (int i=1; i<=n; i++) {
        int vi, wi;
        cin >> vi >> wi;
        for (int j=vi; j<=v; j++) {
            f[i][j] = max(f[i-1][j], f[i-1][j-vi]+wi);
        }
    }
    cout << f[n][v] << "\\n";
    return 0;
}

// AC
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, v;
    cin >> n >> v;
    vector<vector<int>> f(n+1, vector<int>(v+1, 0));
    for (int i=1; i<=n; i++) {
        int vi, wi;
        cin >> vi >> wi;
        for (int j=0; j<=v; j++) {
            if (j>=vi) f[i][j] = max(f[i-1][j], f[i-1][j-vi]+wi);
            else f[i][j] = f[i-1][j];
        }
    }
    cout << f[n][v] << "\\n";
    return 0;
}

// AC
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, v;
    cin >> n >> v;
    vector<vector<int>> f(n+1, vector<int>(v+1, 0));
    for (int i=1; i<=n; i++) {
        int vi, wi;
        cin >> vi >> wi;
        for (int j=0; j<vi; j++) {
            f[i][j] = f[i-1][j];
        }
        for (int j=vi; j<=v; j++) {
            f[i][j] = max(f[i-1][j], f[i-1][j-vi]+wi);
        }
    }
    cout << f[n][v] << "\\n";
    return 0;
}

优化空间复杂度，使用滚动数组，自动将f[i-1][] → f[i][]

// [<https://www.acwing.com/problem/content/2/>](<https://www.acwing.com/problem/content/2/>)

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, v;
    cin >> n >> v;
    vector<int> f(v+1);
    for (int i=1; i<=n; i++) {
        int vi, wi;
        cin >> vi >> wi;
        for (int j=v; j>=vi; j--) {
            f[j] = max(f[j], f[j-vi]+wi);
        }
    }
    cout << f[v] << "\\n";
    return 0;
}

初始化的问题，有的题目要求恰好装满背包，有的则不需要背包装满。

要求恰好装满背包,那么在初始化时除了 $f[0]$ 为 0,其它 $f[1...V]$ 均设为负无穷，这样就可以保证最终得到的$f[V]$是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将$f[0…v]$全部设为 0。

完全背包

给出背包容量$V$，$N$件物品，每件物品的体积为$v_i$, 价值为$w_i$，每件物品能选无数次或不选，选取物品总体积不超过$V$的情况下，最大总价值是多少？

定义$f[i,v]$为前$i$件物品放入一个容量为$v$的背包可以获得的最大价值。$f[N,V]$为所求。

$$ f[i,v]=max\{f[i-1, v-k\cdot c_i]+k\cdot w_i|0\le k\cdot c_i \le v\} $$

状态$f[i,v]$的求解时间是$O(\frac{v}{c_i})$，总求解时间复杂度为$O(NV\sum \frac{V}{c_i})$

// <https://www.acwing.com/problem/content/3/>

// TLE
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, v;
    cin >> n >> v;
    vector<vector<int>> f(n+1, vector<int>(v+1, 0));
    for (int i=1; i<=n; i++) {
        int vi, wi;
        cin >> vi >> wi;
        // for (int j=0; j<=v; j++) {
        //     f[i][j] = f[i-1][j];
        // }
        for (int j=0; j<=v; j++) {
            for (int k=0; k*vi<=j; k++) {
                f[i][j] = max(f[i][j], f[i-1][j-k*vi]+k*wi);
            }
            
        }
    }
    cout << f[n][v] << "\\n";
    return 0;
}

优化

$\begin{array}{lll} f[i,v]& = & max\{f[i-1, v-k\cdot c_i]+k\cdot w_i|0\le k\cdot c_i \le v\} \\ & = & max\{f[i-1, v], f[i-1, v- c_i]+w_i, \cdots, f[i-1, v-\lfloor \frac{v}{c_i} \rfloor \cdot c_i]+\lfloor \frac{v}{c_i} \rfloor\cdot w_i\} \\ \end{array}$

$\begin{array}{lll} f[i,v-c_i]& = & max\{f[i-1, v-c_i-k\cdot c_i]+k\cdot w_i|0\le k\cdot c_i \le v-c_i\} \\ & = & max\{f[i-1, v-c_i], f[i-1, v- 2c_i]+w_i, \cdots, f[i-1, v-c_i-(\lfloor \frac{v}{c_i} \rfloor-1) \cdot c_i]+(\lfloor \frac{v}{c_i} \rfloor-1)\cdot w_i\} \\ \end{array}$