动态规划学习笔记

~~待更新~~ <---这辈子是不会更新了

背包动态规划

01背包

有(N)件物品和一个容量为(V)的背包。第(i)件物品的费用是(c[i])，价值是(w[i])。求解将哪些物品装入背包可使价值总和最大。

(f[i][j])表示前(i)件物品恰放入一个容量为(j)的背包可以获得的最大价值，转移方程为

[f[i][j]=max{f[i-1][j],f[i-1][j-v[i]]+w[i]} ]

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= m; j++) {
		if(j < v[i]) f[i][j] = f[i - 1][j];
		else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
	}
}

空间复杂度优化（压维）

for(int i = 1; i <= n; i++) {
	for(int j = t; j >= 0; j--) {
		if(j >= w[i]) {
			f[j] = max(f[j - v[i]] + w[i], f[j]);
		}
	}
}

完全背包

有(N)种物品和一个容量为(V)的背包，每种物品都有无限件可用。第(i)种物品的费用是(c[i])，价值是(w[i])。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

比01背包多一层枚举即可

for(int i = 0; i < n; i++) {
	for(int j = 0; j <= m; j++) {
		for(int k = 0; k * v[i] <= j; k++) {
			f[i][j] = max(f[i][j], f[i - 1][j - k * v[i] + k * w[i]);
		}
	}
}

多重背包

有(N)种物品和一个容量为(V)的背包。第(i)种物品最多有(a[i])件可用，每件费用是(c[i])，价值是(w[i])。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

用(f[i][j])表示考虑前(i)种物品，一共用了(j)的费用的价值，则转移方程为

[f[i][j] = max_{k <= a[i]}(f[i - 1][j - c[i] * k] + w[i] * k) ]

for(int i = 0; i < n; i++) {
	for(int j = 0; j <= m; j++) {
		for(int k = 0; k <= a[i]; k++) {
			f[i][j] = max(f[i][j], f[i - 1][j - k * v[i] + k * w[i]);
		}
	}
}

复杂度(O(N * V * a[i]))，不满足要求

想优化！用二进制优化，转化为01背包问题