文章

39

粉丝

74

获赞

1

访问

19.0k

头像
简单背包问题 题解:dp
P1035
发布于2024年3月22日 16:06
阅读数 600

#include <stdio.h>
#include <stdlib.h>
int s,n;
int w[1000];
int dp[1000][1000];

int max(int a,int b)
{
    if(a>=b)return a;
    else return b;
}

int main()
{
    while(scanf("%d%d",&s,&n)!=EOF)
    {
        //dp[i][j]放前i个物品,能不能刚好装下容量为j的物品
        for(int i=0; i<n; i++)scanf("%d",&w[i]);
        for(int i=0; i<=s; i++)dp[0][i]=0;
        dp[0][w[0]]=1;
        for(int i=0; i<n; i++)dp[i][0]=1;

        for(int i=1; i<n; i++)
        {
            for(int j=1; j<=s; j++)
            {
                if(dp[i-1][j]==1)dp[i][j]=1;
                else if(dp[i-1][j-w[i]]==1&&j>=w[i])dp[i][j]=1;
                else dp[i][j]=0;

            }

        }
        if(dp[n-1][s]==1)printf("YES\n");
        else printf("NO\n");
    }



    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发