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

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