- /*任务:
- Sample Input
- 100 395 12030 3010 10
- Sample Output
- 120
- */
- 代码实现:
- #include<stdio.h>
- #include<string.h>
- int c[20][1000];
- int knapsack(int m,int n)
- {
- int i,j,w[21],p[21];
- for(i=1;i<n+1;i++)
- scanf("%d%d",&w[i],&p[i]);
- memset(c,0,sizeof(c));
- for(i=1;i<n+1;i++)
- {
- for(j=1;j<m+1;j++)
- {
- if(w[i]<=j)
- {
- if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
- c[i][j]=p[i]+c[i-1][j-w[i]];
- else
- c[i][j]=c[i-1][j];
- }
- else
- c[i][j]=c[i-1][j];
- }
- }
- return(c[n][m]);
- }
- int main()
- {
- int m,n;
- while(scanf("%d%d",&m,&n)!=EOF)
- {
- printf("%d\\n",knapsack(m,n));
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/300120131999.html
来源: http://www.codesnippet.cn/detail/300120131999.html