问题描述
已知n个物品和一个背包容量为C，物品i(i=1,2,3,......)的容量为c[i]
价值w[i]。
物品i可以装入，也可以不装入，但是不可以拆分。如何设计装包使得装包
总效益最大。
动态规划逆推求解
设dp[i,j]为背包容量j，可取物品的范围为i，i+1，i+2，......n的最大效益值。
即这是从后往前作为递推的方向。也就是思考怎么从i+1这个状态转移到i的状态
无非是放入和不放两种情况。
这里：
当 j<c[i]的时候 物品无法放入。最大效益值为dp[i+1,j]相同。
当 j>=c[i]的时候 会出现两个选择：
（1）不放入物品i 最大效益值为dp[i+1,j]
（2）放入物品i 这个时候的最大效益是 dp[i+1,j-c[i]]+w[i]
这里我们期望的最大效益是这两者中的最大值。
因此这个递推方程为 dp[i,j]=max{ dp[i+1,j] ,dp[i+1,j-c[i]]+w[i]
}
这个方程全面一点就是
这里既可以安装上面的思路推出，也可以 由dp[i,j]=max{ dp[i+1,j]
,dp[i+1,j-c[i]]+w[i] }
想到j>c[i]才可以保证结果是大于0
从而想到需要比较j和c[i]的大小。从而得出完整的递推关系式。
#include<stdio.h>
#include<string.h>
int main()
{
int n,c,p[50],w[50],m[50][500],dp[500];
//参数输入
printf("请物品的个数和背包的总重量：");
scanf("%d%d",&n,&c);
for(int
i=1;i<=n;i++)
{
printf("输入w%d
p%d:",i,i);
scanf("%d%d",&w[i],&p[i]);
}
//递推
//初始化的操作
//注：如数组没有初始化 则其值是随机的
for(int j=0;j<=c;j++)
{
if(j>=w[n]) m[n][j]=p[n];
else m[n][j]=0;
}
//使用递推关系
for(int i=n-1;i>=1;i--)
for(int j=0;j<=c;j++)
{
if(j>=w[i]&&m[i+1][j-w[i]]+p[i]>m[i+1][j])
m[i][j]=m[i+1][j-w[i]]+p[i];
else
m[i][j]=m[i+1][j];
}
printf("最大值：%d\n",m[1][c]);
return
0;
｝
动态规划顺推求解
设dp[i,j]为背包容量为j，可选的物品为1,2,3,....i的时候的最大效益。
从前往后递推，有i-1状态转移到i状态。
#include<stdio.h>
#include<string.h>
int
main()
{
int n,c,p[50],w[50],m[50][500],dp[500];
//参数输入
printf("请物品的个数和背包的总重量：");
scanf("%d%d",&n,&c);
for(int
i=1;i<=n;i++)
{
printf("输入w%d
p%d:",i,i);
scanf("%d%d",&w[i],&p[i]);
}
//顺推
//初始化
for(int j=0;j<=c;j++)
{
if(j>=w[1]) m[1][j]=p[1];
else m[1][j]=0;
}
//利用递推关系
for(int i=2;i<=n;i++)
for (int j=0;j<=c;j++)
{
if(j>=w[i]&&m[i-1][j]<m[i-1][j-w[i]]+p[i])
m[i][j]=m[i-1][j-w[i]]+p[i];
else
m[i][j]=m[i-1][j];
}
pritf("%d",m[n][c])
return 0;
}
对于初始化，可以直接全部赋值为0即可。第二次循环从w[i]开始
#include<cstdio>
#include<cstring>
#include<algorithm>
using
namespace std;
int n,c,p[50],w[50],m[50][500],dp[500];
int
main()
{
//参数输入
printf("请物品的个数和背包的总重量：");
scanf("%d%d",&n,&c);
for(int
i=1;i<=n;i++)
{
printf("输入w%d
p%d:",i,i);
scanf("%d%d",&w[i],&p[i]);
}
memset(m,0,sizeof(m));
for(int i=1;i<=n;i++)
for(int j=c;j>=w[i];j--)
m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+p[i]);
printf("%d",m[n][c]);
return
0;
}
进一步的思考
上面的思维实际是背包的从前往后 以及从后往前的比较。这里进一步想一想
程序实际是两个for循环，我们上面实际都是对i 从前往后和从后往前。
能不能这里对j也有两种遍历呢？
在这篇博客里面引入了一个问题。就是将二位数组降低为一维。
再降维的时候 我们只能将第二个循环从大到小进行遍历。原因是如果从小往大遍历就会覆盖。
一维的程序很容易写成：
dp[j] =max { dp[j] , dp[j-c[i]+w[i]] }
参考《背包九讲》于是伪代码是：
for i=1......N
for v=V......0
dp[v]=max{dp[v],dp[v-c[i]]+w[i]}
其实这个代码还是有点抽象的，
在真正编程的时候应该这么去写:
for i=1......N
for v=V......0
if(v>=c[i]) dp[v]=max(dp[v],dp[v-c[i]]+w[i]);
else dp[v]=dp[v];
这个时候我们很清楚的就可以看到了 在v<c[i]的时候 实际上dp[v]是没有发生变化的。
因此我们可以减少这一步的操作。将v = V......c[i]进一步加一优化。
for i=1.........N
for v=V......c[i]
dp[v]=dp[v]>dp[v-c[i]]+w[i]?dp[v]:dp[v-c[i]]+w[i];
同时关于初始化的细节，《九讲》里面也说得很不错。
如果是背包必须装满即最后的最大值为V。那么初始化 dp[0]=0, dp[1.....V]=-INF
如果可以不装满 那么只用memset(dp,0,sizeof(dp))全部初始化为0.