(完全背包) $O(n^2)$
集合划分
y总视频里面的划分方式:f(i, j)中第i个物品选0, 1, 2, … k - 1, k个然后再推一遍公式再得出一个结论
我感觉其实没有必要这么麻烦,我们可以这样看:首先将集合划分为两个1. 不选择i,2. 按照选了k个i后,j的值进行划分 那么第二个集合中可以有f(i, j - vi * 1), f(i, j - vi * 2), f(i, j - vi * 3) …,该集合中j的序列是一个差为vi的等差数列,
综上,第一个集合和第二个集合根据选i和不选i划分对映到变量i,第二个集合中的集合根据
i选了几个后的j的值划分,对应变量j,不重不漏,我们选择当前物品的时候只会用到其中的两个集合一个是f(i - 1, j),一个是f(i, j - vi * 1),这样就不用去推公式了^^
我们求出来的f(0, 0)到f(i, j),在下一次的f(i, j + 1)中都当成已知量,直接拿来用
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, f[N];
int v[4] = {10, 20, 50, 100};
int main(void) {
cin >> n;
f[0] = 1;
for(int i = 0; i < 4; ++i) {
for(int j = v[i]; j <= n; ++j) {
f[j] += f[j - v[i]];
}
}
cout << f[n] << endl;
return 0;
}