分组背包问题

题目背景：$N$ 组物品， 背包容量是 $V$ ，每组物品最多只能选一个。

符号表示：每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号， $j$ 是组内编号。 $k[\ \ \ ]$记录各组内物品数量

状态表示：$dp[\ \ \ ]$ 一维。

状态转移：在01背包基础上多了一个对组内遍历求最优解。

代码如下：

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

解释：对于每个组（line1），从最大容量逆序遍历，对相同的容量（line2），将 $dp[\ \ j\ \ ]$ 更新为最大价值。

我遇到的问题：但是如果一组里有物品：体积为1的价值为2，体积为2的价值为5，那逆序下来，j大于1时都是选体积为2的，但j=1时肯定选体积为1的，这时候一个组里的物品不就选了两个吗？

解答：$\textcolor{cYan}{关键点： dp[i][j] 表示的是前 i 组，容量为 j 的书包的最大价值}$。确实 $dp[1]$ 用的是体积为1的物品， $dp[j\geq 2]$ 用的是体积为2的物品，但这不影响，因为：

• 数组倒序遍历，并且是对相同的 $j$ 将组内所有物品遍历完再去更新 $j-1$ 的值。这保证了不会利用到被组内其他成员污染后的值。
• 这个数组是组内竞争后的结果，每个 $dp[j]$ 都代表了对于前 $i$ 组中，$j$ 能容纳的最大价值，并且都是在$dp[i-1][\ \ \ ]$ 上只加上一个 $i$ 组内的值。