讨论 / c语言-背包问题AC代码
llqxs 2017-01-06 08:44:39
点我顶贴 收藏 删除
#include<stdio.h>

#define max(a,b) a>b?a:b

int h[30];

main()

{

int c,n,i,j;

scanf("%d%d",&c,&n);

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

scanf("%d",&h[i]);

int a[n+1][c+1];

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

for(j=0; j<=c; j++)

a[i][j]=0;

for(j=0; j<=c; j++)

if(h[1]<=j)a[1][j]=h[1];

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

for(j=0; j<=c; j++)

if(j<h[i])a[i][j]=a[i-1][j];

else a[i][j]=max(a[i-1][j],a[i-1][j-h[i]]+h[i]);

int max1=0;

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

for(j=0; j<=c; j++)

if(a[i][j]<=c)

max1=max1>a[i][j]?max1:a[i][j];

printf("%d",max1);

}

查看更多回复
提交回复