大佬们说这是dp的一个非常简单的入门,但是遇到难一点的背包还是不懂啊,dp真的好难啊.
写的比较好的博客
对于最普通的01背包,还是比较简单的,尽量用一维的去做,更加好理解和好用.具体看代码吧.
(一二维都写下吧,也可以对比)
一维
for(int i=1;i<=m;i++)//m代表有m个物品
for(int j=tot;j>=w[i];j--)//tot表示总体积. //如果剩下的体积大于将要放的体积,才放赛.
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
//dp[i]表示背包体积为i时的最大价值,只有一层层的dp下去就可以找到体积最大时价值最高为多少.
二维
dp[i][v]=max( dp[i-1][j],dp[i-1][j-w[i]]+v[i] )
对于这方方程其实并不难理解，方程之中，现在需要放置的是第i件物品，这件物品的体积是w[i],价值是v[i],因此f[i-1][j]代表的就是不将这件物品放入背包，而dp[i-1][j-w[i]]+v[i]则是代表将第i件放入背包之后的总价值，比较两者的价值，得出最大的价值存入现在的背包之中。
for(i=1;i<=m;i++){
for(j=0;j<=tot;j++){
if(j>=w[i])//如果放的下的话才放.
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//如果可以更新就更新.
else
dp[i][j]=dp[i-1][j];//否则就不更新.
}
}
题也多,还需要加深做题和理解啊!!!
根据滚动数组原理,可以对这个背包问题进行空间压缩(一维滚不起来(因为空间不允许,自己想想),只好滚二维).
二维滚动数组背包(因为当前状态只被上一层的状态所影响,所以可以用滚动数组)
int dp[2][maxn];
for(int i=1;i<=m;i++){
for(int j=0;j<=tot;j++){
if(j>=w[i])
dp[i%2][j]=max(dp[(i-1)%2][j],dp[(i-1)%2][j-w[i]]+v[i]);
else
dp[i%2][j]=dp[(i-1)%2][j];
}
}
printf("%d\n",dp[m%2][tot]);
不管几维,最重要的是你想好每一维的状态代表什么,状态转移方程是什么,这样你才能做的出来这种题.
