大意：有一个容量为$c$的背包，有$n$个$s_1$类物体，价值都为$k_1$，体积分别为$s_{1,1}, s_{1,2}, \cdots, s_{1,n}$，有$m$个$s_2$类物体，价值都为$k_2$体积分别为$s_{2,1}, s_{2,2}, \cdots, s_{2,m}$，求背包能装下的最大价值。（价值的计算方法：$k_i * (c - s_i)$）
分析
背包问题，但又要 先做贪心的处理，为什么可以贪心呢？因为有这样一个事实，对于同一类物品，肯定是优先放体积小的，因为体积小r就大，因此先对两类物品按照体积分别排序。
所以最终选的物品的结果肯定是第一类物品的前i项，第二类物品的前j项 $（i,j >= 0）$
所以我们可以很轻松地定义DP中的“状态”了。定义dp[i][j]为取了第一类物品的前i项，第二类物品的前j项 所获得的价值。
状态转移方程 ：
$dp[i][j] = max \{ dp[i-1][j] + (C - Sum1[i] - Sum2[j] )*k1 , dp[i][j-1] + (C - Sum2[j] - Sum1[i] )*k1 \} $，
其中$Sum1 $是第一类物品体积前缀和，$Sum2$ 是第二类物品体积前缀和。
原文：https://www.cnblogs.com/lfri/p/11181638.html