背包问题

01背包

\(N\)件物品，背包容量\(V\)，第\(i\)件消耗\(C_i\)，得到\(W_i\)，求\(\mathbb{MAX}(\sum W)\)。

每种物品仅有一件，选择放或不放。

\(F[i, v]\) 表示前\(i\)件物品恰放入容量\(v\)的背包可获得最大价值。 \[ F[i,v]=\mathbb{MAX}\{F[i-1,v],F[i-1,v-C_i]+W_i\} \] Algorithm

\(\mathbb{INIT}~~v \in [0,V] \Rightarrow F[0,v]=0\)

\(\mathbb{CYCLE}~~i \in [1,N] \Rightarrow v \in [C_i,V] \Rightarrow F[i,v]=\mathbb{MAX}\{F[i-1,v],F[i-1,v-C_i]+W_i\}\)

一维数组优化保证第\(i\)次循环结束后\(F[v]\)等价于\(F[i, v]\)。 \[ F[v]=\mathbb{MAX}\{F[v],F[v-C_i]+W_i\} \]

递减计算\(F[v]\)能保证计算时\(F[v − C_i ]\)保存的是状态\(F[i − 1, v − C_i]\)的值，防止覆盖。

第\(i\)次循环中的状态\(F[i, v]\)是由状态\(F[i − 1, v − C_i ]\)递推而来，这是为了保证每件物品只选一次，保证在考虑选入第\(i\)件物品策略时，依据一个不可能已经选入第\(i\)件物品的子状态\(F[i − 1, v − C_i]\)。

Algorithm

\(\mathbb{INIT}~~v \in [0,V] \Rightarrow F[v]=0\)

\(\mathbb{CYCLE}~~i \in [1,N] \Rightarrow v \in [V,C_i] \Rightarrow F[v]=\mathbb{MAX}\{F[v],F[v-C_i]+W_i\}\)

要价格尽量大：\(\mathbb{INIT}~~v \in [0,V] \Rightarrow F[0,v]=0\)

要求恰好装满：\(\mathbb{INIT}~~F[0]=0,v \in [1,V] \Rightarrow F[v]=-\infin\)

初始化\(F\)数组事实上是在没有任何物品可以放入背包时的合法状态，如果要求背包恰好装满，只有容量为\(0\)的背包可以在什么也不装且价值为\(0\)的情况下被恰好装满，其它容量的背包均无合法解，被赋值为\(-\infin\)。

Example

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
// 二维
bool canPartition(vector<int>& nums) {
	int n = nums.size();
	int sum = accumulate(nums.begin(), nums.end(), 0);
	if (sum & 1) return false;
	sum >>= 1;
	vector<vector<int>> dp(n + 1, vector<int>(sum + 1));
	for (auto& i : dp[0]) {
		i = 0;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = nums[i - 1]; j <= sum; ++j) {
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
		}
	}
	return dp[n][sum] == sum;
}

// 一维
bool canPartition(vector<int>& nums) {
	int n = nums.size();
	int sum = accumulate(nums.begin(), nums.end(), 0);
	if (sum & 1) return false;
	sum >>= 1;
	vector<int> dp(sum + 1, 0x80000000);
    dp[0] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = sum; j >= nums[i - 1]; --j) {
			dp[j] = max(dp[j], dp[j - nums[i - 1]] + nums[i - 1]);
		}
	}
	return dp[sum] == sum;
}

完全背包

\(N\)种物品，背包容量\(V\)，第\(i\)种消耗\(C_i\)，得到\(W_i\)，每种可无限放，求\(\mathbb{MAX}(\sum W)\)。

\(F[i, v]\) 表示前\(i\)件物品恰放入容量\(v\)的背包可获得最大价值。 \[ F[i,v]=\mathbb{MAX}\{F[i-1,v-kC_i]+kW_i,k \in [0,\frac{v}{C_i}]\} \] 若两种物品\(i、j\)满足\(C_i \le C_j,W_i \ge W_j\)，则物品\(j\)不用考虑。

01背包思路，利用二进制，把第\(i\)种物品拆成费用\(C_i2^k\)、价值为\(W_i2^k\)的若干件物品。 \[ k \in [0,\mathop{log_2}\frac{V}{C_i}] \] Algorithm

\(\mathbb{INIT}~~v \in [0,V] \Rightarrow F[v]=0\)

\(\mathbb{CYCLE}~~i \in [1,N] \Rightarrow v \in [C_i,V] \Rightarrow F[v]=\mathbb{MAX}\{F[v],F[v-C_i]+W_i\}\)

完全背包特点是每种物品可选无限件，所以在考虑加选一件第\(i\)种物品策略时，需要一个可能已选入第\(i\)种物品的子状态\(F[i − 1, v − C_i]\)，所以必须采用\(v\)递增的顺序循环。

多重背包

\(N\)种物品，背包容量\(V\)，第\(i\)种消耗\(C_i\)，得到\(W_i\)，每种有\(M_i\)件，求\(\mathbb{MAX}(\sum W)\)。

\(F[i, v]\) 表示前\(i\)种物品恰放入容量\(v\)的背包可获得最大价值。 \[ F[i,v]=\mathbb{MAX}\{F[i-1,v-kC_i]+kW_i,k \in [0,M_i]\} \] 第\(i\)种物品换成\(M_i\)件01背包中的物品即可用01背包思路求解。（不推荐）