问题:有 $N$件物品和一个容量是 $W$ 的背包。每件物品只能使用一次。第 $i$ 件物品的体积是 $v_i$,价值是 $w_i$。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。

输入:

第一行两个整数,$N$, $V$, 用空格隔开,分别便是物品数量和背包容积。接下来的$N$ 行,没行两个整数表示物品体积和价值

输出:

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


0-1背包问题是指每一种物品都只有一件,可以选择放或者不放。现在假设有n件物品,背包承重为m。

对于这种问题,我们可以采用一个二维数组去解决:f[i][j],其中i代表加入背包的是前i件物品,j表示背包的承重,f[i][j]表示当前状态下能放进背包里面的物品的最大总价值。那么,f[n][m]就是我们的最终结果了。

采用动态规划,必须要知道初始状态和状态转移方程。初始状态很容易就能知道,那么状态转移方程如何求呢?对于一件物品,我们有放进或者不放进背包两种选择:

  1. 假如我们放进背包,f[i][j] = f [i - 1][j - weight[i]] + value[i],这里的f[i - 1][j - weight[i]] + value[i]应该这么理解:在没放这件物品之前的状态值加上要放进去这件物品的价值。而对于f[i - 1][j - weight[i]]这部分,i - 1很容易理解,关键是 j - weight[i]这里,我们要明白:要把这件物品放进背包,就得在背包里面预留这一部分空间。
  2. 假如我们不放进背包,f[i][j] = f[i - 1][j]。

因此,我们的状态转移方程就是:f[i][j] = max(f[i][j] = f[i - 1][j] , f[i - 1][j - weight[i]] + value[i])

当然,还有一种特殊的情况,就是背包放不下当前这一件物品,这种情况下f[i][j] = f[i - 1][j]。

算法一: 二维动态规划


/*
f[i][j] 表示只看前i个物品,总体积是j情况下,总价值最大是多少

result = max(f[n][0~V])

f[i][j]:

1.不选第 i 个物品. f[i][j] = f[i-1][j];
2.选第 i 个物品. f[i][j] = f[i-1][j-v[i]] + w[i];

f[i][j] = max{f[i-1][j], f[i-1][j-v[i]] + w[i]}

f[0][0] = 0

空间使用: 4 * 1000000 /1024 /1024 = 4MB
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

算法二: 一维数组优化

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m;
int f[N];
int v[N], w[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]);
            }
        }
/*
f[0] = 0;
f[i] = 0;

k < m;

f[k] = max_w;
f[0] = 0 => f[v[0]] = w[0] => ... 

f[m-k] = 0 => f[m-k+v[0]] = w[0] => ...
*/
    
    cout << f[m] << endl;
    return 0;
}

说明:在一位数组情况下,因为不同状态都是用同一数组保存的,为了数组更新时使用的数据都是前一状态,因此第二个for循环需要从最大容量向最小容量遍历。