01背包

//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;
int T, M, tim[105], vl[105], dp[1005];//背包重量，物品个数，物品重量，物品价值 
int main(){
	cin >> T >> M;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= M; i++){
		cin >> tim[i] >> vl[i];
	}
	dp[0] = 0;
	for (int i = 1; i <= M; i++){
		for (int j = T; j >= tim[i]; j--){
			dp[j] = max(dp[j], dp[j - tim[i]] + vl[i]);
		}
	}
	cout << dp[T] << endl;
	return 0;
}

输入：

70 3
71 100
69 1
1 2

输出：

3

完全背包

//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;
int m, n, wei[35], vl[35], dp[205]; //背包重量，物品个数，物品重量，物品价值 
int main(){
	cin >> m >> n;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; i++){
		cin >> wei[i] >> vl[i];
	}
	dp[0] = 0;
	for (int i = 1; i <= n; i++){
		for (int j = wei[i]; j <= m; j++){
			dp[j] = max(dp[j], dp[j - wei[i]] + vl[i]);
		}
	}
	cout << dp[m] << endl;
	return 0;
}

输入：

10 4
2 1
3 3
4 5
7 9

输出：

12

多重背包

//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;
int n, V, v[105], w[105], cnt, f[105]; //物品数量，背包重量，物品重量，物品价值，新的物体数 
int main(){
	cin >> n >> V;
	int a, b, s; //s表示物体个数 
	for (int i = 1; i <= n; i++){
		cin >> a >> b >> s;
		int k = 1; //枚举个数
		while (k <= s){ //将每个物体按二进制合成 
			v[++cnt] = k * a;
			w[cnt] = k * b;
			s -= k;
			k *= 2;
		} 
		if (s){ //还留着 
			v[++cnt] = s * a;
			w[cnt] = s * b;
		}
	}
	for (int i = 1; i <= n; i++){ //就是01背包 
		for (int j = V; j >= v[i]; j--){
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << f[V] << endl; 
	return 0;
}

INPUT:

4 5
1 2 3
2 4 1
3 4 3
4 5 2

OUTPUT:

10

分组背包

//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;
int n, m, x, cnt, wei[10005], vl[10005], group[10005], dp[10005];//物品个数,背包重量,组数,总组数,物品重量,物品价值,小组中的物品个数 
int ids[205][205]; //ids[i][j]表示组数i中物品j的编号 
int main(){
	cin >> m >> n;
	for (int i = 1; i <= n; i++){
		cin >> wei[i] >> vl[i] >> x;
		cnt = max(cnt, x);
		group[x]++;
		ids[x][group[x]] = i;
	}
	for (int i = 1; i <= cnt; i++){
		for (int j = m; j >= 0; j--){
			for (int k = 1; k <= group[i]; k++){
				if (j >= wei[ids[i][k]]){
					dp[j] = max(dp[j], dp[j - wei[ids[i][k]]] + vl[ids[i][k]]);
				}
			}
		}
	}
	cout << dp[m] << endl;
	return 0;
}

INPUT:

45 3
10 10 1
10 5 1
50 400 2

OUTPUT:

10