rnqoj-39-饮食问题-01背包

01简单背包

#include<stdio.h>
int dp[50001];
int a[1001];
int main()
{int i,j,c,b;scanf("%d%d",&c,&b);for(i=0;i<b;i++)scanf("%d",&a[i]);dp[0]=1;for(i=0;i<b;i++){for(j=c;j>=a[i];j--){if(dp[j]==0)dp[j]=dp[j-a[i]];}}for(j=c;j>=0;j--){if(dp[j]){printf("%d\n",j);break;}}return 0;
}