您当前位置：首页 > 互联网 > HDU 3535 AreYouBusy(混合背包)

HDU 3535 AreYouBusy(混合背包)

来源：程序员人生发布时间：2014-11-07 08:57:46 阅读次数：2891次

HDU3535 AreYouBusy(混合背包)

http://acm.hdu.edu.cn/showproblem.php?pid=3535

题意:

给你n个工作集合，给你T的时间去做它们。给你m和s，说明这个工作集合有m件事可以做，它们是s类的工作集合（s=0,1,2，s=0说明这m件事中最少得做1件，s=1说明这m件事中最多只能做1件，s=2说明这m件事你可以做也能够不做）。再给你ci和gi代表你做这件事要用ci的时间，能取得gi的快乐值。求在T的时间内你能取得的最大快乐值。

分析:

首先如果存在最优解, 我们可以互换不同工作集合的处理顺序, 仍然能得到最优解. 那末我们下面只需要处理每一个单独的工作集合便可.

令dp[i][j]==x表示处理完前i组工作集,所花时间<=j时的快乐值为x。每得到1组工作就进行1次DP，所以dp[i]为第i组的结果。下面对3种情况进行讨论。

1. 该集合内最少要选1件工作时. 要保证最少选1个第i类工作, 可以从第i⑴类的结果dp[i⑴]来更新dp[i].也能够用 01背包的思想, 从本类的前1个工作更新后1个工作.

初始化:dp[i]全为负无穷.(即-INF)

状态转移方程为:

dp[i][k]=max{dp[i][k],dp[i⑴][k-cost[j]]+val[k],dp[i][k-cost[j]]+val[j] }

2. 该集合内最多选1件工作时. 只能从上1层的结果dp[i⑴]来更新dp[i]了.(想一想为何)

初始化:dp[i]==dp[i⑴].

状态转移方程为dp[i][k]=max{dp[i][k],dp[i⑴][k-cost[j]]+val[k]}.

3. 该集合内工作可以随意选. 这就是1个普通的01背包问题了.

初始化:dp[i]==dp[i⑴].

状态转移方程为:

dp[i][k]=max{dp[i][k],dp[i⑴][k-cost[j]]+val[k],dp[i][k-cost[j]]+val[j] }

终究所求:dp[n][t]的值.

AC代码:

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100+5; #define INF 1e8 int n; int t; int dp[maxn][maxn]; int cost[maxn]; int val[maxn]; int main() { while(scanf("%d%d",&n,&t)==2) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { int m,s; scanf("%d%d",&m,&s); for(int k=1;k<=m;k++) scanf("%d%d",&cost[k],&val[k]); if(s==0)//最少选1个的01背包问题 { for(int j=0;j<=t;j++) dp[i][j]=-INF; for(int k=1;k<=m;k++) for(int j=t;j>=cost[k];j--) { dp[i][j] = max( dp[i][j] , dp[i][j-cost[k]]+val[k] ); //1 dp[i][j] = max( dp[i][j] , dp[i⑴][j-cost[k]]+val[k] );//2 //上面两句顺序互换就会出错!为何? } } else if(s==1)//最多选1个的背包问题 { for(int j=0;j<=t;j++) dp[i][j]=dp[i⑴][j]; for(int k=1;k<=m;k++) for(int j=t;j>=cost[k];j--)//j可以正序或逆序枚举 dp[i][j] = max( dp[i][j] , dp[i⑴][j-cost[k]]+val[k] ); } else if(s==2)//随意选的01背包问题 { for(int j=0;j<=t;j++) dp[i][j]=dp[i⑴][j]; for(int k=1;k<=m;k++) for(int j=t;j>=cost[k];j--)//j只能逆序枚举 dp[i][j] = max( dp[i][j] , dp[i][j-cost[k]]+val[k] ); } } int ans = max(dp[n][t],⑴); printf("%d ",ans); } return 0; }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 HTML――上中下布局

下一篇 漫谈并发编程(三)：共享受限资源

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点