程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> Hdu 3535 AreYouBusy(DP_背包)

Hdu 3535 AreYouBusy(DP_背包)

編輯:關於C

題目大意:xiaoA想盡量多花時間做ACM,但老板要求他在t時間內做完n堆工作,每個工作耗時cost[i][j],幸福感val[i][j],每個工作有num[i]個工作,每堆工作都有一個性質,0表示至少要做裡面的1個工作,1表示最多做裡面的1個工作,2表示隨意,做或不做都行。最後問在符合老板要求的情況下的最大幸福感,怎麼都不符合要求就輸出-1.

解題思路:這是混合背包嗎?尼瑪的這樣混合我的狀態轉移方程都沒辦法寫了。
    可以把每堆工作當做一個組,然後每個組有自己的狀態轉移方程;
    當某組的性質為0時是分組背包變形,每次狀態從前一組獲當前組轉移而來,能從一個地方轉移而來,這組就合法。
    當某組的性質為1時,就是分組背包,但這裡是用二維數組,在一組計算完成之後,要把前一組的結果復制下來。
    當某組的性質為2時,就把這組當成01背包來做,也要記得把前一組的結果復制下來,因為本組可以不選。
    本題有個trick,那就是容量是從0開始的,和常規的容量從1開始不一樣,要注意for循環裡的下界。

測試數據:
1 0
2 0
0 1
0 2


1 0
2 2
0 1
0 2


1 1000
2 0
1 1
2 2

代碼:
[cpp]
#include <stdio.h> 
#include <string.h> 
#define MAX 102 
#define max(a,b) (a) > (b) ? (a) : (b) 
 
 
int ans,dp[MAX][MAX]; 
int n,m,num[MAX],flag[MAX]; 
int cost[MAX][MAX],val[MAX][MAX]; 
 
 
int Solve_1A() { 
 
    int i,j,k,tpval; 
 
 
    dp[0][0] = 0; 
    for (i = 1; i <= n; ++i) { 
         
        if (flag[i] == 2) { 
            //01背包 www.2cto.com  
            for (k = 1; k <= num[i]; ++k) 
                for (j = m; j >= cost[i][k]; --j) { 
                     
                    tpval = dp[i][j-cost[i][k]]; 
                    if ( tpval != -1) dp[i][j] = max(dp[i][j],tpval+val[i][k]); 
                    tpval = dp[i-1][j-cost[i][k]]; 
                    if ( tpval != -1) dp[i][j] = max(dp[i][j],tpval+val[i][k]); 
                 
                } 
            for (j = 0; j <= m; ++j) 
                dp[i][j] = max(dp[i][j],dp[i-1][j]); 
        } 
        else if (flag[i] == 1) { 
            //分組背包,最多選一個,保證dp[i][j]只由上一次的一個狀態轉移而來 
            for (j = m; j >= 0; --j) 
                for (k = 1; k <= num[i]; ++k)  
                    if (j >= cost[i][k]) { 
                     
                        tpval = dp[i-1][j-cost[i][k]]; 
                        if (tpval != -1) dp[i][j] = max(dp[i][j],tpval+val[i][k]); 
                    } 
            for (j = 0; j <= m; ++j) 
                dp[i][j] = max(dp[i][j],dp[i-1][j]); 
        } 
        else { 
            //至少選一個的分組背包 
            for (k = 1; k <= num[i]; ++k) 
                for (j = m; j >= cost[i][k]; --j) { 
                     
                    tpval = dp[i][j-cost[i][k]]; 
                    if (tpval != -1) 
                        dp[i][j] = max(dp[i][j],tpval+val[i][k]);  
                    tpval = dp[i-1][j-cost[i][k]]; 
                    if (tpval != -1)  
                        dp[i][j] = max(dp[i][j],tpval+val[i][k]);  
                 
                } 
        } 
 
        //本組不合法,可直接返回-1 
        for (j = 0; j <= m; ++j) 
            if (dp[i][j] != -1) break; 
        if (j == m + 1) return -1; 
    } 
 
     
    for (ans = -1,i = 0; i <= m; ++i) 
        ans = max(ans,dp[n][i]); 
    return ans; 

 
 
int main() 

    int i,j,k,t,tpval; 
 
 
    while (scanf("%d%d",&n,&m) != EOF) { 
 
        memset(dp,-1,sizeof(dp)); 
        memset(num,0,sizeof(num)); 
        for (i = 1; i <= n; ++i) { 
 
            scanf("%d%d",&num[i],&flag[i]); 
            for (j = 1; j <= num[i]; ++j) 
                scanf("%d%d",&cost[i][j],&val[i][j]); 
        } 
 
 
        int ans = Solve_1A(); 
        printf("%d\n",ans); 
    } 

 


摘自 ZeroClock

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved