首页 > 代码库 > [HDU 3535] AreYouBusy (动态规划 混合背包)
[HDU 3535] AreYouBusy (动态规划 混合背包)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3535
题意：有n个任务集合，需要在T个时间单位内完成。每个任务集合有属性，属性为0的代表至少要完成1个，属性为1的为至多完成1个，属性为2的为任意完成。
每个任务做完后都有个价值，问在T个时间单位内完成n个任务集合的任务获得的最大价值是多少？如果不能满足要求输出-1
首先先分析什么情况下输出-1：
因为属性为0的代表至少要完成1个，当遇到一个属性为0的任务集合里一个都无法完成的时候，输出-1.
其他的属性不予考虑，因为其中的每个任务都是可完成可不完成的。
那么问题就归结成为了：属性为0的，是一个分组背包，属性为1的是一个分组背包，属性为2的在组内是一个01背包。
这道题目的好处就是在于深入理解各种背包，我就是不太理解，所以刚开始就敲的各种挫，WA了好多次。
代码：
1 import java.util.*; 2 3 public class Main{ 4 public static void main(String[] args){ 5 Scanner sc = new Scanner(System.in); 6 while( sc.hasNext() ){ 7 int n = sc.nextInt(); 8 int T = sc.nextInt(); 9 int [][][] c = new int[n+1][111][2];10 11 for(int i=1;i<=n;i++){12 c[i][0][0] = sc.nextInt();13 c[i][0][1] = sc.nextInt();14 for(int j=1;j<=c[i][0][0];j++){15 c[i][j][0] = sc.nextInt();16 c[i][j][1] = sc.nextInt();17 }18 }19 20 int dp[][] = new int[n+1][111];21 22 23 24 boolean flag = true;25 26 for(int i=1;i<=n;i++){27 if( c[i][0][1]==0 ){28 Arrays.fill(dp[i], -99999999);29 for(int k=1;k<=c[i][0][0];k++){30 for(int j=T;j>=c[i][k][0];j--){31 dp[i][j] = Math.max(dp[i][j], Math.max(dp[i-1][j-c[i][k][0]]+c[i][k][1],dp[i][j-c[i][k][0]]+c[i][k][1]));32 }33 }34 if( dp[i][T]<0 ) flag = false;35 } else if( c[i][0][1] == 1 ){36 for(int j=T;j>=0;j--){37 dp[i][j] = dp[i-1][j];38 for(int k=1;k<=c[i][0][0];k++){39 if( j>=c[i][k][0]) dp[i][j] = Math.max(dp[i][j], dp[i-1][j-c[i][k][0]]+c[i][k][1]);40 }41 }42 } else if( c[i][0][1] == 2 ){43 for(int j=T;j>=0;j--){44 dp[i][j] = dp[i-1][j];45 }46 for(int k=1;k<=c[i][0][0];k++){47 for(int j=T;j>=c[i][k][0];j--){48 dp[i][j] = Math.max(dp[i][j], dp[i][j-c[i][k][0]]+c[i][k][1]);49 }50 }51 }52 53 } // for i54 55 if( flag ) System.out.println(dp[n][T]);56 else System.out.println(-1);57 58 }59 }60 }
[HDU 3535] AreYouBusy (动态规划 混合背包)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。