B - ACboy needs your help
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit Status
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.
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
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0
Sample Output
3
4
6
题意:
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 ;
}