分析
对于每一个物品,在背包容量足够的情况下,我们有两种状态,一种是把该物品放在背包,一种是不把该物品放在背包。
我们建立一个二维的数组,$dp[ i ][ j ]$表示前$i$ 个物品,在容量为$j$ 的时候的最大价值。
$V[ i ]$ 表示物品所占的体积 ,$W[ i ]$ 表示物品的价值
- 不把该物品放在背包:$dp[ i ][ j ] = dp[ i - 1][ j ]$,我们直接顺延上一个物品选择的结果
- 把该物品放在背包:$dp[ i ][ j ]=max(dp[ i ][ j ],dp[i-1] [ j-V[ i ] ] + W[ i ])$
因为要把这个物品放在背包,所以背包中首先得有该物品的容量大小。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N][N];
int V[N],W[N];//物品所占的体积,物品所占的价值
int main()
{
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 = 0; j <= m; j++)
{
dp[i][j] = dp[i-1][j];//不选当前物品
//选当前物品
if(j >= V[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-V[i]] + W[i]);
}
cout<<dp[n][m]<<endl;
return 0;
}
在动态规划中,对于这种当前状态只与前一层的状态有关的情况,我们就可以对数组进行压缩,可以把二维变成一维。
改进后
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N];
int V[N],W[N];
int main()
{
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--)
dp[j] = max(dp[j], dp[j - V[i]] + W[i]);
cout<<dp[m]<<endl;
return 0;
}
拓展问题
上面的问题求的是,背包中物品的总价值最大,但是此时背包确是不一定满的。
如果问题改为,求背包中物品的体积之和恰好为背包的容量的时候,怎么做呢?我们可以在初始化的时候做点手脚。
通过改进后,我们就可以确保$dp[ n ]$的值是从初始状态转移过来的。也就是背包中物品体积恰好为背包体积时,背包中物品的最大价值,