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;}