HDU1712 ACboy needs your help

ACboy needs your help

题目链接ACboy needs your help


题目大意
有n个课程，现在花m天来学习这些课程，学习每个课程花的天数不同所得到的价值不同，求m天怎么分配学习课程才能得到的价值最大

解题思路
分组背包问题
把每门课程看做是每一组，每一组里面最多选择一个天数，对于每一组都是一个01背包，三重循环即可，三重循环每一重循环意义见代码注释

附上代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF=0x3f3f3f;
int dp[105],a[105][105];
int main(){
 ios::sync_with_stdio(0);
 cin.tie(0);cout.tie(0);
 
 int n,m;
 while(cin>>n>>m&&(n||m)){
  memset(dp,0,sizeof dp);
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)
    cin>>a[i][j];
  for(int i=1;i<=n;i++){//分组数 
   for(int j=m;j>=1;j--){//容量体积  
    for(int k=1;k<=j;k++)//属于i组的k值
     dp[j]=max(dp[j],dp[j-k]+a[i][k]);
   }
  }
  cout<<dp[m]<<endl;
 }
 return 0;
}