HDOJ 1712 ACboy needs your help(分組0/1背包)

把同一門考試當成一組，在一門考試裡，花的天數和考的成績分別是組內物品的代價和價值，這樣就轉化成一個分組的0/1背包的問題。

AC程序：

[cpp]
/*HDOJ1712
作者：陳佳潤
2013-04-19
*/ 
#include<iostream>  
using namespace std; 
#include<string.h>  
#define max(a,b) (a>b?a:b)  
int groud[105]; 
int dp[105]; 
int m; 
void ZeroOnePack(){ 
    int k,i; 
    for(i=m;i>0;i--){//對於每一個天數  
        for(k=1;k<=m;k++){//對於組內每一個物品  
            if(i>=k) 
                dp[i]=max(dp[i],dp[i-k]+groud[k]); 
        } 
    } 
} 
 
int main(){ 
    int n,i,j; 
    //freopen("1.txt","r",stdin);  
    while(cin>>n>>m&&(n!=0||m!=0)){ 
        memset(dp,0,sizeof(dp)); 
        for(i=1;i<=n;i++){//對於每一門考試  
            for(j=1;j<=m;j++){ 
                cin>>groud[j]; 
            } 
            ZeroOnePack(); 
        } 
        cout<<dp[m]<<endl; 
    } 
    return 0; 
} 

/*HDOJ1712
作者：陳佳潤
2013-04-19
*/
#include<iostream>
using namespace std;
#include<string.h>
#define max(a,b) (a>b?a:b)
int groud[105];
int dp[105];
int m;
void ZeroOnePack(){
 int k,i;
 for(i=m;i>0;i--){//對於每一個天數
  for(k=1;k<=m;k++){//對於組內每一個物品
   if(i>=k)
    dp[i]=max(dp[i],dp[i-k]+groud[k]);
  }
 }
}

int main(){
 int n,i,j;
 //freopen("1.txt","r",stdin);
 while(cin>>n>>m&&(n!=0||m!=0)){
  memset(dp,0,sizeof(dp));
  for(i=1;i<=n;i++){//對於每一門考試
   for(j=1;j<=m;j++){
    cin>>groud[j];
   }
   ZeroOnePack();
  }
  cout<<dp[m]<<endl;
 }
 return 0;
}