转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
非常综合的背包。
必须得有较好的01背包和完全背包基础,对于分组背包要有非常好的了解。
三种情况,0表示每组中至少取一个,1表示每组中至多取一个,2表示随意取,其实就是01背包了。
对于每组至少取一个:dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][k].cost]+a[i][k].val,dp[i][j-a[i][k].cost]+a[i][k].val)); 由于dp[i][j]初始化为-inf,如果一个都不取的话,还是-inf,直接导致后面的没法再取,能保证至少取一个,对于可以取多个,只需要改变循环顺序,对于每一个容量,遍历所有物品。
对于至多取一个:就是普通的分组背包,可能不取,就是dp[i-1][j],之后就按普通的分组背包。
对于随意取:就是普通的01背包,不取的话就是dp[i-1][j],之后便是小组内的01背包
有一组数据是
1 10
2 1
0 1
0 2
答案是2,得注意,费用可能为0的情况。
如果有多个费用为0的情况,对于至多取一个的情况,会重复计算。
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-6
#define LL long long
#define LD long double
#define pi acos(-1.0)
#define inf 1<<29
using namespace std;
struct Node{
int cost,val;
}tmp;
vector<Node>a[105];
int n,t,m,kind[105];
int dp[105][105];
bool cmp(Node n1,Node n2){
return n1.cost!=n2.cost?n1.cost<n2.cost:n1.val>n2.val;
}
int main(){
while(scanf("%d%d",&n,&t)!=EOF){
for(int i=1;i<=n;i++){
a[i].clear();
scanf("%d%d",&m,&kind[i]);
for(int j=0;j<m;j++){
scanf("%d%d",&tmp.cost,&tmp.val);
a[i].push_back(tmp);
}
}
for(int i=0;i<=n;i++)
for(int j=0;j<=t;j++)
dp[i][j]=-inf;
dp[0][0]=0;
for(int i=1;i<=n;i++){
if(kind[i]==0){
for(int k=0;k<a[i].size();k++)
for(int j=t;j>=0;j--)
if(j-a[i][k].cost>=0)
dp[i][j]=max(dp[i][j],max(dp[i-1][j-a[i][k].cost]+a[i][k].val,dp[i][j-a[i][k].cost]+a[i][k].val));
}
else if(kind[i]==1){
for(int j=0;j<=t;j++)
dp[i][j]=dp[i-1][j];
sort(a[i].begin(),a[i].end(),cmp);
for(int j=t;j>=0;j--)
for(int k=0;k<a[i].size();k++)
if(k!=0&&a[i][k].cost==0)
continue;
else if(j-a[i][k].cost>=0)
dp[i][j]=max(dp[i][j],dp[i-1][j-a[i][k].cost]+a[i][k].val);
}
else{
for(int j=0;j<=t;j++)
dp[i][j]=dp[i-1][j];
for(int k=0;k<a[i].size();k++)
for(int j=t;j>=0;j--)
if(j-a[i][k].cost>=0)
dp[i][j]=max(dp[i][j],dp[i][j-a[i][k].cost]+a[i][k].val);
}
}
int ans=-1;
for(int i=0;i<=t;i++)
ans=max(ans,dp[n][i]);
if(ans<0)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码