【Luogu P1164】小A点菜

2024-08-30 02:57:59

题目原链接：

Luogu 小A点菜

【解题思路】

常规的0-1背包，不过是求装满整个背包的方案数，只要把0-1背包的状态转移方程稍微改一下就行。因为要求方案数，那么把方程中的max换成sum就行。

【解题反思】

要注意变量的含义和题目所问的问题

【参考程序】

#include<iostream>

#include<cstdio>

using namespace std;

int v,n,a[200005],f[10002];

int main()

{

    cin>>v>>n;//v是菜品数量，n是神犇兜兜里装的钱

    for (int i=1;i<=v;i++) cin>>a[i];

    f[0]=1;//0元也是一种方案

    for (int i=1;i<=v;i++)

        for (int j=n;j>=a[i];j--)//要注意j>=a[i]

            f[j]+=f[j-a[i]];//加上去就好

    cout<<f[n];//输出

    return 0;

}

最新文章

热门文章