C++ 代码

//
// Created by zrz on 2021/4/22.
//
/*
 * 背包问题解题步骤总结归纳 : 1.确定背包容量
 *                          2.输入
 *                          3.对于每一种物品进行枚举
 *                          4.对于背包容量进行枚举(至此状态计算完毕)
 *                          5.输出
 */
#include <iostream>
#include <cstring>
using namespace std;

const int N = 25010;//把货币面值a[i]看成是背包大小

int f[N];//f[i]表示面值是i的货币的所有可选组成方案的个数
int a[110];//储存货币面值

int main()
{
    int t;
    cin >> t;

    while (t --)//t个测试样例
    {
        int n;
        cin >> n;
        memset(f,0,sizeof f);//每次都要初始化数组
        memset(a,0,sizeof a);
        int m = 0;
        int k = 0;
        for (int i = 0;i < n;i ++)//输入每一种货币面值
        {
            cin >> a[i];
            k = max(k,a[i]);//取最大的货币面值为k,并把k作为背包容量
        }

        //求count的背包问题必须初始化,不然全0
        f[0] = 1;
        for (int i = 0;i < n;i ++)//枚举每一种货币
            for (int j = a[i];j <= k;j ++)//枚举背包容量
                f[j] = f[j] + f[j - a[i]];//求count

        for (int i = 0;i < n; i ++)//枚举每一种货币面值
        {
            if (f[a[i]] == 1) m ++;//如果组成面值为a[i]的货币的可选方案个数为1,说明它只能由自己组成自己,而不能被其它货币表示,所以必须选它
        }

        cout << m << endl;
    }

}

```