hdu1712 ACboy needs your help

hdu1712 ACboy needs your help

​​ Problem 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 3 4 6

Source HDU 2007-Spring Programming Contest 我的做法是设dp[i][j]表示当前做到第i号物品我一共花时间为j 那么注意当我循环的时候我需要从大往小 因为这样保证我 并没有被更新过 此外还需要注意有可能当前做的可能是上一次顺延下来的 看递推方程：dp[j]=max(dp[j],dp[j-c[k]]+w[k]);（其中c[k]为k物品的费用，w[k]为价值），由于递降枚举背包容量（第二重循环），dp[j-c[k]]在本组物品中是未进行过决策的，亦即背包容量为j-c[k]时，在本组物品中是没有选择任何物品的，这可以保证对dp[j]决策时，不会多选本组中的物品。 复杂度应该是O(nm2)的

#include#include#include#define N 110using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}int n,m,dp[N][N],a[N][N];int main(){ freopen("hdu1712.in","r",stdin); while(1){ n=read();m=read();if (!n&&!m) return 0; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) a[i][j]=read(); memset(dp,0,sizeof(dp)); for (int i=1;i<=n;++i){ for (int j=m;~j;--j){ dp[i][j]=max(dp[i-1][j],dp[i][j]); for (int k=1;k<=j;++k){ dp[i][j]=max(dp[i][j],dp[i-1][j-k]+a[i][k]); } } }printf("%d\n",dp[n][m]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。