多重背包

问题

---

给定$n$个物品和一个容量为$W$的背包，对于第$i$个物品有重量$w[i]$和价值$v[i]$以及数量$cnt[i]$。选择若干个物品放入背包中，在不超过背包最大容量的情况下，求背包中物品价值之和的最大值。

过程

---

多重背包可以将第$i$个物品看成$cnt[i]$个重量为$w[i]$，价值为$v[i]$的不同类物品，然后对每个物品进行0-1背包即可。
二进制分解优化：对于任何一个正整数$n$，都可以拆解为多个2的幂次方的和。例如$7=2^0+2^1+2^2$，1到7之间的数都可以由$2^0=1$，$2^1=2$，$2^2=4$组合而成，又比如$10=2^0+2^1+2^2+3$。因此可以将第$i$个物品拆分成${\log }_{2}n$个物品，然后对所有物品进行0-1背包即可。

实现

---

一维滚动数组

int N, M;
int n;
int w[N], v[N], cnt[N];
int dp[N][M];
 
void knapspack()
{
	for(int i = 1; i <= n; i++)
		for(int k = 1; k <= cnt[i]; k++)
			for(int j = W; j >= w[i]; j--) // 逆序
				dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
}

二进制分解

int N, M;
struct item
{
	int w, v;
} items[N];
int n;
int w[N], v[N], cnt[N];
int dp[M];
 
void knapspack()
{
	vector<item> items;
	for(int i = 1; i <= n; i++)
	{
		for(int k = 1; k <= cnt[i]; k *= 2)
		{
			items.push_back({k * w[i], k * v[i]});
			cnt[i] -= k;
		}
		if(cnt[i] > 0) // 余数直接当做一个物品
			items.push_back({cnt[i] * w[i], cnt[i] * v[i]});
	}	
	
	for(item i : items)
		for(int j = W; j >= i.w; j--) // 逆序
			dp[j] = std::max(dp[j], dp[j - i.w] + i.v]);
}

题目

---