背包小结(01背包 + 完全背包 + 多重背包)
首先来比较下三个问题!!
【01背包】
给你n种不同的物品,每个物品有自己的重量w[i],和价值v[i],如果每个物品只能拿一次,给你容量为m的背包,怎样才能取得最大价值?
【完全背包】
给你n种不同的物品,每个物品有自己的重量w[i],和价值v[i],一个物品可以拿多次,给你容量为m的背包,怎样才能取得最大价值?
【多重背包】
给你n种不同的物品,每个物品有自己的重量w[i],和价值v[i],如果每个物品最多只能拿c[i]个,给你容量为m的背包,怎样才能取得最大价值?
主要是物品数量的差别!!!
----------------------------
【01背包】
给你n种不同的物品,每个物品有自己的重量w[i],和价值v[i],如果每个物品只能拿一次,给你容量为m的背包,怎样才能取得最大价值?
状态转移方程:dp[j]=MAX{dp[j],dp[j-w[i]]+v[i]}
基本操作:
for(i=0;i<n;i++)
for(j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
dp[j]用来记录当容量为j时的可行取法的最大价值。
例题:
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int t,n,m,i,j;
int v[1005],w[1005];
int dp[1005];
scanf("%d",&t);
while(t--)
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&v[i]);
for(i=0;i<n;i++)
scanf("%d",&w[i]);
for(i=0;i<n;i++)
for(j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
printf("%d\n",dp[m]);
}
return 0;
}
-------------------------------
【完全背包】
给你n种不同的物品,每个物品有自己的重量w[i],和价值v[i],一个物品可以拿多次,给你容量为m的背包,怎样才能取得最大价值?
分析:类似于01背包问题,在01背包问题中,物品要么取,要么不取,而在完全背包中,物品可以取0件、取1件、取2件...直到背包放不下位置。因此,可以直接在01背包的递推式中扩展得到。
状态转移方程:dp[j]=MAX{dp[j],dp[j-w[i]]+v[i]}
基本操作:
for(i=1;i<=n;i++)
for(j=w[i];j<=m;j++) //注意此处与01背包不同,01为倒序
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
一个简单有效的优化
完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高得j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。
-------------------------------
【多重背包】
给你n种不同的物品,每个物品有自己的重量w[i],和价值v[i],如果每个物品最多只能拿c[i]个,给你容量为m的背包,怎样才能取得最大价值?
状态转移方程:dp[j]=MAX{dp[j],dp[j-k*w[i]]+k*v[i]};
基本操作:
for(i=1;i<=n;i++)
for(j=m;j>=0;j--)
for(k=0;k<=c[i];k++)
{
if(j-k*w[i]<0) break;
dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
}
-------------------------------
再也不是一无所知的dp盲了馁!!!在这里感谢*队友!!!
上一篇: P1094 纪念品分组