优化成一维后 从小到大 循环

for (int i = 1; i <= n; i ++)
    for (int j = v[i]; j <= m; j ++) // 完全背包是从小到大枚举，这样可以使一个物品可以被选多次
        f[j] = max(f[j], f[j - v[i]] + w[i]);

货币系统

思路:$b_i$一定属于$a_i$, 且$b_i$不能被集合$b$中的元素表示出来

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 25005;

int T;
int n, a[N];
bool f[M];

int main()
{
    cin >> T;

    while (T --)
    {
        cin >> n;
        for (int i = 0; i < n; i ++) cin >> a[i];
        sort(a, a + n);

        int m = a[n - 1]; // 以最大的元素为体积上限
        memset(f, 0, sizeof f);
        f[0] = true;
        int res = 0;
        for (int i = 0; i < n; i ++)
        {
            if (!f[a[i]]) res ++; // 如果当前元素还不能被比它更小的元素表示出,说明这是一个必要元素
            for (int j = a[i]; j <= m; j ++)
                f[j] |= f[j - a[i]];
        }
        cout << res << endl;
    }
    return 0;
}