分析

这是简单背包问题。这里背包的值只能为0或者1。0代表有 i 个菜，j 的钱时，没有能在 i 个菜中凑出总价为 j 的方案；1反之。

代码

#include <stdio.h>

int main()
{
    int n, k;
    int dp[36][10005] = {0};//定义背包二维数组，并赋初值0；值只能为0或1；0表示无解，1表示有解
    dp[0][0] = 1;//前0个菜中能凑出满足价格为0的方案，所以为1
    int a[36];
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
    }
    for(int i=1; i<=n; i++)
    {
        for(int j = 0; j <=k; j++)
        {
            if(dp[i-1][j] == 1)//当不算上第i个菜已经有解，则算上第i个菜也有解
                dp[i][j] = 1;
            if(j >= a[i] && dp[i-1][j-a[i]] == 1)//当总价钱能买下第i个菜，且dp[i-1][j-a[i]] == 1
                dp[i][j] = 1;
        }
    }
    if(dp[n][k] == 1)
        printf("yao bu ni bie gan le ba");
    else
        printf("wo bu yao ni jue de,wo yao wo jue de");
    return 0;
}