前置知识：分组背包 由于每组的物品是互斥的，在进行背包dp时，对于每个给定的背包容量，我们只能在当前组别选一件物品。 滚动数组优化后：设dp[j]为容量为j时取得的最大价值，当前考虑到第i组。 如果这一组有k个物品，第l个物品的空间是w[l],价值为c[l]，那么我们的状态转移方程为 dp[j]=max{dp[j],dp[j−w[1]]+c[1],dp[i−w[2]]+c[2],...,dp[j−w[k]]+c[k]}dp[j] = max\{dp[j],dp[j-w[1]]+c[1],dp[i-w[2]]+c[2], ... ,dp[j-w[k]]+c[k]\} dp[j]=max{dp[j],dp[j−w[1]]+c[1],dp[i−w[2]]+c[2],...,dp[j−w[k]]+c[k]} 对比01背包 可以将01背包看成每一组只有一个物品的分组背包，则对于当前物品(w,c)的状态转移方程为 dp[j]=max{dp[j],dp[j−w]+c}dp[j] = max\{dp[j],dp[j-w]+c\} dp[j]=max{dp[j],dp[j−w]+c} 如果每组有两个，则转移方程为 dp[j]=max{dp[j],dp[j−w[1]]+c[1],dp[j−w[2]]+c[2]}dp[j] = max\{dp[j],dp[j-w[1]]+c[1],dp[j-w[2]]+c[2]\} dp[j]=max{dp[j],dp[j−w[1]]+c[1],dp[j−w[2]]+c[2]} 那么如果每组有k个，就能得到上文给出的分组背包的状态转移方程。(不难发现，每组的k不一样也无所谓) 下面我们来分析这道题：