分析

这是一个简单背包问题。推荐学习视频：https://www.bilibili.com/video/BV1AJ411Y7Fm?p=29

代码

#include <stdio.h>
#include <string.h>

int main()
{
    int dp[100][100] = {0};//定义背包数组。值只为0或1；0表示不可以，1表示可以
    int w[100];//定义重量数组
    int s, n;
    while(scanf("%d%d", &s, &n)!=EOF)
    {
        int i, j;
        for(i=1; i<=n;i++)
        {
            scanf("%d", &w[i]);
        }
        dp[0][0] = 1;//前0件物品中能凑出满足重量为0的方案，所以为1
        for(i=1; i<=n; i++)
        {
            for(j=0; j<=s; j++)
            {
                if(dp[i-1][j] == 1)//当不算上第i件物品已经有解，则算上也有解
                    dp[i][j] = 1;
                if(j - w[i] >= 0 && dp[i-1][j-w[i]] == 1)//当背包能装下第i件物品，且dp[i-1][j-w[i]]==1
                    dp[i][j] = 1;
            }
        }
        if(dp[n][s] == 1)
            printf("yes!\n");
        else
            printf("no!\n");
    }
    return 0;
}