简单的背包问题
背包问题动态规划中非常经典的一个问题，本文只包含01背包，完全背包和多重背包。更加详尽的背包问题的讲解请参考崔添翼大神的《背包九讲》
简单的01背包
- 问题导入：新年到了，mjl马上就要外出旅游。mjl拥有一个容量为P的小背包，他希望在自己的n件体积为Vi的物品中带走的物品体积之和尽可能的多，他最多能带走多少物品？（每件物品只有一个）
- 问题分析：可以创建一个二维数组dp[i][j]，使用0和1表示对于前i件物品是否能凑出j的体积。要判断dp[i][j]的值是否为true，可以查看dp[i-1][j-V[i]]即前i-1件物品是否能凑出j-V[i]的重量出来或者dp[i-1][j]即前i-1件物品已经可以把体积j凑出来。
- 代码实现：
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1; i<=n; i++)
{
for(int j=p; j>=v[i]; j--)
{
if(dp[i-1][j-v[i]] || dp[i-1][j])
{
dp[i][j] = 1;
}
}
}
int ans;
for(int i=p; i>=0; i--)
{
if(dp[n][j])
{
ans = j;
break;
}
}
注意代码中从后向前更新dp[i][j]，是为了防止一件物品被使用多次
对于简单01背包问题的优化
显然，在简单01背包问题中，空间复杂度达到了O(n*p)之多。而在每一次更新第i行的数据时，只需要i-1行的数据即可,再向上的数据完全可以舍弃，所以只需要开一个两行的二维数组即可。
01滚动：
- 只存在第0行和第一行，每次更新数据后将第1行的数据复制到第0行
- 代码实现：
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1; i<=n; i++)
{
for(int j=p; j>=v[i]; j--)
{
if(dp[0][j-v[i]] || dp[0][j])
{
dp[1][j] = 1;
}
}
for(int i=0; i<=n; i++)
{
dp[0][i] = dp[1][i];
}
}
int ans;
for(int i=p; i>=0; i--)
{
if(dp[1][j])
{
ans = j;
break;
}
}
尽管01滚动的空间复杂度已经优化了很多，但是每一次结束后的复制操作增加了时间复杂度。同时最终对于结果有用的只是最后一行，因此有一种优化空间的同时不影响时间复杂度的优化方法，即使用一位数组就地滚动
就地滚动：
- 只使用一个一位数组，每一次在原来数组的基础上更新数据
- 代码实现：
memset(dp,0,sizeof(dp));
dp[0] = 1;
for(int i=1; i<=n; i++)
{
for(int j=p; j>=v[i]; j--)
{
if(dp[j-v[i]] == 1)
{
dp[j] = 1;
}
}
}
int ans;
for(int i=p; i>=0; i--)
{
if(dp[i] == 1)
{
ans = i;
break;
}
}
01背包
- 问题导入：既然外出旅游，当地的纪念品当然是必不可少的，因此mjl来到了景区内的一家纪念品商店。众所周知，景区的商店往往都是黑店，mjl身上的钱并不能买下他喜欢的所有东西，他对于每一件纪念品做了一个评分，评分越高代表他越喜欢这件纪念品，现在mjl想知道他能带走商品的最大评分和是多少,其中价格为p[i]，评分为v[i],携带的钱为m。
- 问题分析：这里只需要使用一个二维数组dp[i][j]表示对于前i个物品，当已花费j金钱时能够带走的最大价值。状态转移方程为dp[i][j] = max( dp[i-1][j] , dp[i-1][j-p[i]] + v[i] )。
-代码实现（就地滚动）：
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++)
{
for(int j=m; j>=p[i]; j--)
{
dp[j] = max(dp[j], dp[j-p[i]]+v[i]);
}
}
int ans = 0;
for(int i=m; i>=0; i--)
{
ans = max(ans, dp[i]);
}
printf("%d\n",ans);
完全背包
- 完全背包简单的说就是在01背包的基础上，所有的物品都可以重复购买无限次。既然在01背包中为了防止一件物品被多次使用而从后向前遍历，那么在完全背包中只需要改为从前向后遍历即可
- 代码实现：
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++)
{
for(int j=p[i]; j<=m; j++)
{
dp[j] = max(dp[j], dp[j-p[i]]+v[i]);
}
}
int ans = 0;
for(int i=m; i>=0; i++)
{
ans = max(ans, dp[i]);
}
printf("%d\n",ans);
未完待续……