0-1背包

N件物品，容量为V的背包，每件物品有各自价值且只能被选择一次，求有限背包容量下装入物品总价值最大。

二维版本

  1. 状态f[i][j]定义：前i个物品中，背包容量j下的最大价值。注意：j表示体积。 初始状态f[0][0] = 0
  2. 当前背包容量不够（j < v[i]），没得选。前i个物品的最值为前i-1个的最值。f[i][j] = f[i - 1][j]
  3. 当前背包容量够，存在两种状态：选：f[i][j] = f[i - 1][j - v[i]] + w[i] 不选：f[i][j] = f[i - 1][j]

    代码

    ```cpp

    include

    include

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 = 1; j <= m; j ++) { //从1开始遍历体积 if (j < v[i]) { // 当前背包容量不够 f[i][j] = f[i - 1][j]; } else { // 取选与不选两者中的最大值 f[i][j] = max(f[i - 1][j - v[i]] + w[i], f[i - 1][j]); } } } cout << f[n][m] << endl; return 0; }

  1. <a name="U26Tc"></a>
  2. ### 一维版本
  3. > 二维版本f[i][j]可以求得任意合法的i和j的最优解。只关注最终状态f[n][m]，观察二维公式f[i][j] = f[i - 1][jxxxx],s所以可以采用一维数组。
  5. 1. 初始状态定义改变：N件物品，背包容量j下的最优解。
  6. 1. f[j] = max(f[j], f[i - 1][j - v[i]] + w[i]) 从小到大更新时，如果还是正序，则有f[较小体积]更新到f[较大体积]，有可能本应该用第i -1轮的状态却用的是第i轮的状态。
  7. 1. 例如：一维状态第i轮对体积为3的物品进行决策，f[7] <— f[4] f[4]正确情况下应为f[i - 1][4]， 正序时f[4]此时变成了f[i][4] (循环到第i轮时，f[j]是前i轮中已经决策的物品且背包容量j下的最大值)，此时f[4]被污染，逆序时，f[4]还没有在第i轮计算。
  8. 1. 状态转移方程：f[j] = max(f[j], f[j - v[i]] + w[i]) 
  9. <a name="f4QLT"></a>
  10. #### 代码
  12. - 优化一
  13. ```cpp
  14. #include <iostream>
  15. #include <algorithm>
  17. using namespace std;
  19. const int N = 1010;
  20. int n, m;
  21. int v[N], w[N];
  22. int f[N];
  24. int main() {
  25.     cin >> n >> m;
  26.     for (int i = 1; i <= n; i ++) 
  27.         cin >> v[i] >> w[i];
  28.     for (int i = 1; i <= n; i ++) { //遍历背包数
  29.         for (int j = m; j >= 0; j --) { //从1开始遍历体积 
  30.             if (j < v[i]) { // 当前背包容量不够
  31.                 // f[i][j] = f[i - 1][j]; // 优化前
  32.                 f[j] = f[j];
  33.             } else { // 取选与不选两者中的最大值
  34.                 // f[i][j] = max(f[i - 1][j - v[i]] + w[i], f[i - 1][j]); //优化前
  35.                 f[j] = max(f[j], f[j - v[i]] + w[i]);
  36.             }
  37.         }
  38.     }
  39.     cout << f[m] << endl;
  40.     return 0;
  41. }

  1. 当背包容量大于v[i]时才会更新 循环终止条件可以变更为

    
 for (int i = 1; i <= n; i ++ )
     for (int j = m; j >= v[i]; j -- )
         f[j] = max(f[j], f[j - v[i]] + w[i]);

    ```cpp

    include

    include

using namespace std;

const int N = 1010;

int n, m; //n 物品数量 m 背包体积 int v[N], w[N]; //v 物品的体积 w 物品的价值 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 = m; j >= v[i]; j -- )
        f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;

return 0;

}


1. 处理输入时，一个一个物品，一个一个体积，可以边输入边处理
```cpp
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m; //n 物品数量 m 背包体积
int f[N]; // 最大值

int main()
{
    cin >> n >> m;

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

    return 0;
}

完全背包

N种物品，容量为V的背包，每种物品都有无限件可以使用。

暴力做法 背包问题 - 图2

  • 背包问题 - 图3定义：前i个物品，背包容量j下的最优解。
  • 每一轮循环对第i个物品决策，选择多少个背包问题 - 图4第i件物品。
  • 每次可选取多个重复物品。

    代码

    ```cpp

    include

using namespace std;

const int N = 10010;

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 ++) { int count = j / v[i]; for (int k = 0; k <= count; 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; }

<a name="k9uxc"></a>
### 优化时间 ![](https://cdn.nlark.com/yuque/__latex/f2d5f588234eb61a559ff90c41511b85.svg#card=math&code=O%28n%5E2%29&id=Pgudq)

- 不用计算每个循环第i个物品个数
- f[i][j]定义：前i个物品j体积的最优解。
- 状态方程：![](https://cdn.nlark.com/yuque/__latex/c3d3536636452e573845067f166f9680.svg#card=math&code=f%5Bi%5D%5Bj%5D%20%3D%20max%28f%5Bi%20-%201%5D%5Bj%5D%2C%20f%5Bi%5D%5Bj%20-%20v%5D%20%2B%20w%29&id=Cx91F)
```cpp
#include <iostream>

using namespace std;

const int N = 10010;

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

一维版本

背包问题 - 图5