AreYouBusy HDU - 3535 （混合背包）

本文主要是介绍AreYouBusy HDU - 3535 （混合背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

AreYouBusy

 题目链接：HDU - 3535 

题意：有n个集合，每个集合中由若干任务，集合分为三种类型；0类型表示该集合中的任务至少做一件，1类型表示该集合中的任务最多做一件， 2类型表示该集合中的任务可以随意做；给出每件任务完成所需时间及获得利益，求最大利益；

思路：0类型中每组最少选一件那么让DP数组初始化为-INF可满足，dp[i][j]表示第i组任务，花费j时间获得最大利益；

dp[i][j]=max(dp[i][j], dp[i][j-t]+w, dp[i-1][j-t]+w);

1类型是每组最多选一件，那么dp[i][j]=max(dp[i][j], dp[i-1][j-t]+w);

3类型就是普通01背包了；dp[i][j]=max(dp[i][j], dp[i][j-t]+w);

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int dp[110][110], c[110], g[110];
int main(){int n, T;while(~scanf("%d%d", &n, &T)){int m, s;memset(dp, 0, sizeof(dp));for(int i=1; i<=n; i++){scanf("%d%d", &m, &s);for(int j=1; j<=m; j++){scanf("%d%d", &c[j], &g[j]);}if(s==0){for(int j=0; j<=T; j++)dp[i][j]=-INF;for(int k=1; k<=m; k++){for(int j=T; j>=c[k]; j--){dp[i][j]=max(dp[i][j], max(dp[i][j-c[k]], dp[i-1][j-c[k]])+g[k]);}}}else if(s==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>=c[k]; j--){dp[i][j]=max(dp[i][j], dp[i-1][j-c[k]]+g[k]);}}}else{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>=c[k]; j--){dp[i][j]=max(dp[i][j], dp[i][j-c[k]]+g[k]);}}}}if(dp[n][T]>=0) printf("%d\n", dp[n][T]);else printf("-1\n");}return 0;
}

 

这篇关于AreYouBusy HDU - 3535 （混合背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---