B - ACboy needs your help（动态规划，分组背包）

B - ACboy needs your help

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Description

ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.

Output

For each data set, your program should output a line which contains the number of the max profit ACboy will gain.

Sample Input

2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0

Sample Output

题意:

ACboy有n门课可以参加，他有m天时间。一天只能参加一门课。一门课可以参加多天，参加的天数不同获得的经验不一样，并且一门课只能修习一次。但是要注意的是，同一门课不是参加的天数越多，经验就越高。输入的表示是，行数表示第几门课，列数表示上几天，该数就是第几门课参加几天获得的经验数。问m天能获得最多的经验数。

思路：分组背包，建立dp数组dp[i][j]表示修习前i种课程，修习了j天，所得的最大的经验值。

二维数组：

方法：状态转移方程为dp[i][j]=max{dp[i-1][j],dp[i-1][j-k]+xing[i][k]},意思是前i-1种课程，前j-k天获得的经验最大数是dp[i-1][j-k]，后k天参加第i门课获得的经验是xing[i][k]。比较此时的dp[i][j]和dp[i-1][j-k]+xing[i][k]谁大。

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 using namespace std;

 int dp[][]={};

 int xing[][]={};

 int main()

 {

 //    freopen("1.txt","r",stdin);

     int n,m;

     while(cin>>n>>m&&n!=&&m!=){

         memset(dp,,sizeof(dp));

         int i,j,k;

         for(i=;i<=n;i++){//输入数据

             for(j=;j<=m;j++)

                 cin>>xing[i][j];

         }

         for(i=;i<=n;i++){

             for(j=;j<=m;j++)

             for(k=;k<=j;k++){

                 if(dp[i][j]<=dp[i-][j-k]+xing[i][k])//进行比较

                     dp[i][j]=dp[i-][j-k]+xing[i][k];//状态转移

             }

         }

         cout<<dp[n][m]<<endl;

     }

     return ;

 }

一位数组：

方法：状态转移方程为dp[j]=max{dp[[j],dp[j-k]+xing[i][k]},意思是前j-k天获得的经验最大数是dp[j-k]，后k天参加第i门课获得的经验是xing[i][k]。比较此时的dp[j]和dp[j-k]+xing[i][k]谁大。

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 using namespace std;

 int dp[]={};

 int xing[][]={};

 int main()

 {

 //    freopen("1.txt","r",stdin);

     int n,m;

     while(cin>>n>>m&&n!=&&m!=){

         memset(dp,,sizeof(dp));

         int i,j,k;

         for(i=;i<=n;i++){

             for(j=;j<=m;j++)

                 cin>>xing[i][j];

         }

         for(i=;i<=n;i++){

             for(j=m;j>=;j--)

             for(k=;k<=j;k++){

                 if(dp[j]<=dp[j-k]+xing[i][k])

                     dp[j]=dp[j-k]+xing[i][k];

             }

         }

         cout<<dp[m]<<endl;

     }

     return ;

 }

巴特西

B - ACboy needs your help（动态规划，分组背包）

最新文章

热门文章