算法1

/*
   完全背包问题求方案数：当前方案数 = 取这个物品的方案数 + 不取这个物品的方案数(即上一个状态的方案数) 
*/

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#define MOD 2147483648
using namespace std;
const int maxn = 4005;
typedef unsigned int UI;                 // 可以直接取模(防止爆 int) 
UI bag[maxn],num[maxn],res;               
int n;
int main(void) {
    void knapsack();
    while(scanf("%d",&n) != EOF) {
        memset(bag,0,sizeof(bag));
        res = 0;
        knapsack();
        printf("%u\n",res % MOD);         // 注意: unsigned int 对应的输出形式是 ：%u 
    }
    return 0;
}
void knapsack() {
    bag[0] = 1;                           // 刚开始一个数也没有,也是一种方案 
    for(int i = 1; i <= n; i ++) {
        for(int j = i; j <= n; j ++) {
            bag[j] += bag[j - i] % MOD;
        }
    }
    res = bag[n] - 1;                     // 拿样例来说: 7 本身不符合条件,所以需要减去本身 
    return ;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla