背包问题 9 讲

//f[i][j] 选择的物品是1-i之间,体积为j的最大价值
//
//f[i-1][j] == f[i][j] 意味着 第 i 键物品没有选择
//f[i-1][j] != f[i][j] 意味着选了 第 i 件物品
//
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int a[N][N];
int n, m;
int f[N][N];

// 本质是分组背包
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	// i 给第 i 个公司分配机器
	for (int i = n; i >= 1; i--) {
		for (int j = m; j >= 0; j--) {
			for (int k = 0; k <= j; k++)
				f[i][j] = max(f[i][j], f[i + 1][j - k] + a[i][k]);
		}
	}
	cout << f[1][m] << endl;
	// 输出选择的序列
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (f[i][m] == f[i + 1][m - j] + a[i][j]) {
				cout << i << " " << j << endl;
				m -= j;  // 下一层的机器个数的减少
				break;
			}
		}
	}
	return 0;
}

f[i] 花费 i 元的方案数
f[0] = 1;
for(int i=1;i<=n;i++)
	// f[j] 对应在 1 - i-1 号物品之间的方案数
	for(int j=m;j>=value[i];j--)
		f[j] = f[j] + f[j-value[i]];
// 求方案数的通用公式
// f[j] += f[j-a[i]]

//01 完全， 多重
//01 背包，
//主件， 买或者不买
//附件：前提：买主件，
//0 1 2
//当做分组背包
//按主件分组， 每一个组别里面
//每个一组别， 只选择主件，主件+1.1附件
//	主件+1.2附件
//    主件+2个附件
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
const int M = 32010;
int n, m;
int weight[N], value[N];
int flg[N]; //标记哪个是主件
int f[M];

vector<int> e[N]; // 记录附件所属哪个主件
int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		weight[i] = x;
		value[i] = x * y;
		flg[i] = z;
		if (z != 0)
			e[z].push_back(i);
	}
	// 分组背包
	for (int i = 1; i <= n; i++) {
		if (flg[i] != 0)  // 不是主件，跳过
			continue;
		// 本质是 01 背包
		for (int j = m; j >= 0; j--) {
			// 分类讨论
			if (e[i].size() == 0) { // 当前物品没有附属品
				if (j >= weight[i])
					f[j] = max(f[j], f[j - weight[i]] + value[i]);
			}
			// 当前物品的附属品只有一个
			if (e[i].size() == 1) {
				// 两种情况，只放主件， 放主件 + 附件1
				if (j >= weight[i])  // 只放主件
					f[j] = max(f[j], f[j - weight[i]] + value[i]);
				// 放主件 + 附件 1
				if (j >= weight[i] + weight[e[i][0]]) {
					f[j] = max(f[j], f[j - weight[i] - weight[e[i][0]]] + value[i] + value[e[i][0]]);
				}
			}
			// 当前物品的附属品有两个
			if (e[i].size() == 2) {
				// 两种情况，只放主件， 放主件 + 附件1
				if (j >= weight[i])  // 只放主件
					f[j] = max(f[j], f[j - weight[i]] + value[i]);
				// 放主件 + 附件 1
				if (j >= weight[i] + weight[e[i][0]]) {
					f[j] = max(f[j], f[j - weight[i] - weight[e[i][0]]] + value[i] + value[e[i][0]]);
				}
				// 放主件 + 附件 2
				if (j >= weight[i] + weight[e[i][1]]) {
					f[j] = max(f[j], f[j - weight[i] - weight[e[i][1]]] + value[i] + value[e[i][1]]);
				}
				// 放主件 + 附件 2 + 附件 1
				if (j >= weight[i] + weight[e[i][1]] + weight[e[i][0]]) {
					f[j] = max(f[j], f[j - weight[i] - weight[e[i][1]]  - weight[e[i][0]]] + value[i] + value[e[i][0]] + value[e[i][1]]);
				}
			}
		}
	}
	cout << f[m];
	return 0;
}

二维费用背包
f[i][j] = max(f[i][j] ,f[i-v[i]][j-w[i]] + value[i])

for(i  1-n) 物品个数
	for(int j：V - v[i] ) 背包容量
		for(int k:W - w[i])
			f[j][k] = max(f[j][k] ,f[j-v[i]][k-w[i]] + value[i])

混合背包

01背包
完全背包
多重背包：二进制优化成 01背包
每一个物品的时候判断是 01 还是完全
01 倒着循环， 完全 正着循环

//f[j] 物品质量为j的情况下
//能容纳物品的最大价值
//f[j] :
//不放当前物品，f[j]
//放当前物品 f[j - t[i]] + v[i]
//滚动数组，优化空间
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int M = 1e7 + 10;
int T, n;
int t[N], v[N];
long long f[M];

int main() {
	cin >> T >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i] >> v[i];
	// 完全背包，滚动数组
	for (int i = 1; i <= n; i++)
		for (int j = t[i] ; j <= T; j++)
			f[j] = max(f[j], f[j - t[i]] + v[i]);
	cout << f[T];
	return 0;
}

//n 个草药
//每个草药有时间，价值
//给你固定的时间，
//求能得到的最大价值
//
//动态规划： 找到状态转移方程
//100+ 题以上   可能找到
// t[i] 花费的时间， v[i] 物品对应的价值
// 二维
//f[i][j] 在 1 - i 的物品内选择，在时间 j 内的最大价值 f[i][j]
//考虑第 i 个物品
//每一个物品， 选择当前物品， 放当前物品，预留放当前物品的时间
//f[i - 1][j - t[i]]     j - t[i] 到 j 的时间，相差  t[i]
//f[i - 1] 的时候，第 i 个物品一定是没有被用过的
//不选择当前物品 ： f[i - 1][j]
//
//不用当前物品 ： f[i - 1][j]
//用当前 物品：  f[i - 1][j - t[i]] + v[i]
//求最大值 ， max (f[i - 1][j], f[i - 1][j - t[i]] + v[i])

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
const int M = 1e3 + 10;

int T, n, t[N], v[N];
int f[N][M];


int main() {
	cin >> T >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i] >> v[i];
	for (int i = 1; i <= n; i++) { // 遍历物品的个数
		for (int j = 1; j <= T; j++) { // 遍历时间
			f[i][j] = f[i - 1][j]; // 当前物品不填充
			// 要填充当前物品, 至少得放下当前物品
			if (j >= t[i])
				f[i][j] = max(f[i - 1][j], f[i - 1][j - t[i]] + v[i]);
		}
	}
	cout << f[n][T];
	return 0;
}