0-1背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000

方案1 ——使用二维数组解决0-1背包问题

  1. 二维状态数组f[i][j]：前i个物品，背包容量j下的最优解
  2. 当前背包容量j小于当前物体体积时（j < v[i]），选择不了当前的物体，所以此时最优解为i-1个物品的最优解，即f[i][j] = f[i - 1][j]。
  3. 当前背包容量足够的时候，表明可以选择当前物品，此时会出现两种决策 ，对两种决策取max则为最优解。
    （1）选：f[i][j] = f[i - 1][j - v[i]] + w[i] （先去除当前物体的体积， 然后去上一行找去除i体积的最优解 ，然后加上i的价值）
    （2）不选：f[i][j] = f[i - 1][j]

代码

#include <iostream>
using namespace std;

//二维数组解决 0-1背包
const int N = 1010;
int v[N],w[N]; //体积数组和价值数组
int f[N][N];

int main()
{
    //n为物品数量 m为背包最大容量
    int n,m;
    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++)
        {
            //如果当前容量比i物体的容量小
            if(j < v[i]) f[i][j] = f[i-1][j];
            else f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout << f[n][m] <<endl;
    return 0;
}

方案2 —— 用一维数组优化二维01背包

维度优化的本质是对等式的等价变形。

  1. 为什么可以使用一维数组优化？ 二维数组处理01背包问题都是基于i-1状态进行更新，所以可以引入滚动数组思想，整体只是用上一个状态更新下一次并不会出现跨越多行的情况。
  2. 状态定义f[j] : N件物品，背包容量j下的最优解。
  3. 最关键的不同点：枚举背包容量j从最大容量开始，而不是二维01背包的从小到大遍历。
  4. 为什么需要逆序遍历？ 在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

代码

#include <iostream>
using namespace std;

//二维数组解决 0-1背包
const int N = 1010;
int v[N],w[N]; //体积数组和价值数组
int f[N];

int main()
{
    //n为物品数量 m为背包最大容量
    int n,m;
    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;
}

关于状态f[j]补充说明

二维下的状态定义f[i][j]是前 i件物品，背包容量 j下的最大价值。一维下，少了前 i件物品这个维度，我们的代码中决策到第 i件物品（循环到第i轮），f[j]就是前i轮已经决策的物品且背包容量 j下的最大价值。因此当执行完循环结构后，由于已经决策了所有物品，f[j]就是所有物品背包容量 j下的最大价值。即一维f[j]等价于二维f[n][j]。