本文主要是介绍hdu 3535 AreYouBusy 混合背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
个人感觉思路一点不好想，看了网上的总算是懂了，也自己敲了敲，懂思路就很简单了
题意：
给你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],表示第i组，时间为j时的快乐值。每得到一组工作就进行一次DP，所以dp[i]为第i组的结果。
第一类，至少选一项，即必须要选，那么在开始时，对于这一组的dp的初值，应该全部赋为负无穷，这样才能保证不会出现都不选的情况。
状态转移方程：
dp[i][j]=max(dp[i][j],max(dp[i][j-w[x]]+p[x],dp[i-1][j-w[x]]+p[x]));
dp[i][j]: 是不选择当前工作；
dp[i-1][j-w[x]]+p[x]: 第一次在本组中选物品，由于开始将该组dp赋为了负无穷，所以第一次取时，必须由上一组的结果推知，这样才能保证得到全局最优解；
dp[i][j-w[x]]+p[x]：表示选择当前工作，并且不是第一次取;
第二类，最多选一项，即要么不选，一旦选，只能是第一次选。
状态转移方程：
dp[i][j]=max(dp[i][j],dp[i-1][j-w[x]]+p[x]);
由于要保证得到全局最优解，所以在该组DP开始以前，应该将上一组的DP结果先复制到这一组的dp[i]数组里，因为当前组的数据是在上一组数据的基础上进行更新的。
第三类，任意选，即不论选不选，选几个都可以。
状态转移方程为：
dp[i][j]=max(dp[i][j],dp[i][j-w[x]]+p[x]);
同样要保证为得到全局最优解，先复制上一组解，数据在当前组更新。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 1<<29
using namespace std;
int w[101],p[101];
int dp[101][101];
int main()
{int n,T;while(~scanf("%d %d",&n,&T)){memset(dp,0,sizeof(dp));for(int i=1; i<=n; i++){int m,flag;scanf("%d %d",&m,&flag);for(int x=1; x<=m; x++)scanf("%d %d",&w[x],&p[x]);if(flag==0){for(int j=0; j<=T; j++)dp[i][j]=-INF;for(int x=1; x<=m; x++)for(int j=T; j>=w[x]; j--)dp[i][j]=max(dp[i][j],max(dp[i-1][j-w[x]]+p[x],dp[i][j-w[x]]+p[x]));}else if(flag==1){for(int j=0; j<=T; j++)dp[i][j]=dp[i-1][j];for(int x=1; x<=m; x++)for(int j=T; j>=w[x]; j--)dp[i][j]=max(dp[i][j],dp[i-1][j-w[x]]+p[x]);}else{for(int j=0; j<=T; j++)dp[i][j]=dp[i-1][j];for(int x=1; x<=m; x++)for(int j=T; j>=w[x]; j--)dp[i][j]=max(dp[i][j],dp[i][j-w[x]]+p[x]);}}dp[n][T]=max(dp[n][T],-1);printf("%d\n",dp[n][T]);}return 0;
}
滚动数组解法————>>>滚动数组解释连接点击打开链接
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
int w[101],p[101];
int dp[101],tem[101];
int main()
{int n,T;while(~scanf("%d %d",&n,&T)){memset(dp,0,sizeof(dp));for(int i=1; i<=n; i++){int m,flag;scanf("%d %d",&m,&flag);for(int x=1; x<=m; x++)scanf("%d %d",&w[x],&p[x]);if(flag==0){for(int j=0; j<=T; j++){tem[j]=dp[j];dp[j]=-INF;}for(int x=1; x<=m; x++)for(int j=T; j>=w[x]; j--)dp[j]=max(dp[j],max(dp[j-w[x]]+p[x],tem[j-w[x]]+p[x]));}else if(flag==1){for(int j=0; j<=T; j++){tem[j]=dp[j];}for(int x=1; x<=m; x++)for(int j=T; j>=w[x]; j--)dp[j]=max(dp[j],tem[j-w[x]]+p[x]);}else{for(int x=1; x<=m; x++)for(int j=T; j>=w[x]; j--)dp[j]=max(dp[j],dp[j-w[x]]+p[x]);}}dp[T]=max(dp[T],-1);printf("%d\n",dp[T]);}return 0;
}
这篇关于hdu 3535 AreYouBusy 混合背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
