分组背包

问题

---

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

过程

---

从0-1背包想起，0-1背包是从$n$个物品选择若干个物品，那么问题可以转换为对每一个分组进行0-1背包。但是这样没有解决每个分组最多选择一个的问题。可以将循环顺序进行调整，先逆序遍历重量，再遍历分组内物品，这样就确保了计算$dp[j]=max(dp[j],dp[j-w[i]]+v[i])$时$dp[j]$是按照前一组的结果进行计算，同时$dp[j]$是选择使物品价值最大的一个物品（包括不选）。

实现

---

一维滚动数组

struct item
{
	int w, v;
};
 
int N, M;
int n, W;
vector<item> g[N];
int dp[M];
 
void knapspack()
{
	for(int k = 1; k <= 100; k++)
		for(int j = W; j >= 0; j--)
			for(auto i : g[k])
				if(j >= i.w)
					dp[j] = std::max(dp[j], dp[j - i.w] + i.v);
}