HDU 3535 AreYouBusy(混合背包)
HDU3535 AreYouBusy(混合背包)
http://acm.hdu.edu.cn/showproblem.php?pid=3535
题意:
给你n个工作集合,给你T的时间去做它们。给你m和s。说明这个工作集合有m件事能够做,它们是s类的工作集合(s=0,1,2,s=0说明这m件事中最少得做一件,s=1说明这m件事中最多仅仅能做一件,s=2说明这m件事你能够做也能够不做)。
再给你ci和gi代表你做这件事要用ci的时间,能获得gi的快乐值。
求在T的时间内你能获得的最大快乐值。
分析:
首先假设存在最优解, 我们能够互换不同工作集合的处理顺序, 依旧能得到最优解. 那么我们以下仅仅须要处理每一个单独的工作集合就可以.
令dp[i][j]==x表示处理完前i组工作集,所花时间<=j时的快乐值为x。
每得到一组工作就进行一次DP,所以dp[i]为第i组的结果。以下对三种情况进行讨论。
1. 该集合内至少要选1件工作时. 要保证至少选1个第i类工作, 能够从第i-1类的结果dp[i-1]来更新dp[i].也能够用 01背包的思想, 从本类的前一个工作更新后一个工作.
初始化:dp[i]全为负无穷.(即-INF)
状态转移方程为:
dp[i][k]=max{dp[i][k],dp[i-1][k-cost[j]]+val[k],dp[i][k-cost[j]]+val[j] }
2. 该集合内最多选1件工作时. 仅仅能从上一层的结果dp[i-1]来更新dp[i]了.(想想为什么)
初始化:dp[i]==dp[i-1].
状态转移方程为dp[i][k]=max{dp[i][k],dp[i-1][k-cost[j]]+val[k]}.
3. 该集合内工作能够随便选. 这就是1个普通的01背包问题了.
初始化:dp[i]==dp[i-1].
状态转移方程为:
dp[i][k]=max{dp[i][k],dp[i-1][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-1][j-cost[k]]+val[k] );//2
//上面两句顺序互换就会出错!为什么?
}
}
else if(s==1)//至多选1个的背包问题
{
for(int j=0;j<=t;j++) dp[i][j]=dp[i-1][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-1][j-cost[k]]+val[k] );
}
else if(s==2)//随便选的01背包问题
{
for(int j=0;j<=t;j++) dp[i][j]=dp[i-1][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],-1);
printf("%d\n",ans);
}
return 0;
}
最新文章
- CSS布局——横向两列布局
- SQL存储过程概念剖析
- 常用邮件 smtp pop
- *在Win7中安装JDK1.7并配置环境变量
- POJ 1322 Chocolate
- Redis安装和基础介绍
- 关于jQuery中的选择器
- SpringBoot实现优雅的关机
- OpenBUGS抽样数据基本操作
- ecplise导入项目报错而文件不报错
- LVS(一):基本概念和三种模式
- Division and Union CodeForces - 1101C (排序后处理)
- NSL:CPK_NN神经网络实现预测哪个样本与哪个样本处在同一层,从而科学规避我国煤矿突水灾难—Jason niu
- immutable.js使用总结
- PAT 1004 成绩排名 (20)(代码)
- Nginx、PCRE和中文URL(UTF8编码)rewrite路径重写匹配问题
- 在c#中using和new这两个关键字有什么意义?
- class 类 this指向的问题
- 洛谷 P1281 书的复制
- 2017.2.7 开涛shiro教程-第六章-Realm及相关对象(二)
热门文章
- Wannafly挑战赛22游记
- hdu 5316 Magician(2015多校第三场第1题)线段树单点更新+区间合并
- java中的hashmap与hashtable的区别
- CF961E Tufurama【主席树】
- CodeForces 128D Numbers 构造
- Codeforces Round #280 (Div. 2) E. Vanya and Field 思维题
- antd 父组件获取子组件中form表单的值
- SMB协议概述
- chrome 浏览器 console 加入 jquery 测试调试 一介布衣
- HDU 3726 Graph and Queries (离线处理+splay tree)