|
楼主 |
发表于 2018-2-17 22:42:46
|
显示全部楼层
多重背包和01背包、完全背包的区别:多重背包中每个物品的个数都是给定的,可能不是一个,绝对不是无限个。
将其转化为0-1背包问题
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- struct E
- {
- int w;
- int v;
- }list[2001];
- int dp[101];
- int main()
- {
- int T;
- scanf("%d",&T);
- while(T--)
- {
- int s,n;
- scanf("%d%d",&s,&n);
- int cnt=0;
- for(int i=1;i<=n;i++)
- {
- int v,w,k;
- scanf("%d%d%d",&w,&v,&k);
- int c=1;
- while(k-c>0)
- {
- k-=c;
- list[++cnt].w=c*w;
- list[cnt].v=c*v;
- c*=2;
- }//转化为完全背包问题
- list[++cnt].w=k*w;
- list[cnt].v=k*v;//转化成0-1背包问题
- }
- memset(dp,0,sizeof(dp));
- for(int i=1;i<=cnt;i++)
- for(int j=s;j>=list[i].w;j--)
- dp[j]=max(dp[j],dp[j-list[i].w]+list[i].v);
- printf("%d\n",dp[s]);
- }
- return 0;
- }
复制代码 |
|