我假设每个n项目只能使用一次，并且您必须最大限度地提高利润。
原始的背包是 dp[i] = best profit you can obtain for weight i
for i = 1 to n do
for w = maxW down to a[i].weight do
if dp[w] < dp[w - a[i].weight] + a[i].gain
dp[w] = dp[w - a[i].weight] + a[i].gain
现在，由于我们有两个背包，我们可以使用 dp[i, j] = best profit you can obtain for weight i in knapsack 1 and j in knapsack 2
for i = 1 to n do
for w1 = maxW1 down to a[i].weight do
for w2 = maxW2 down to a[i].weight do
dp[w1, w2] = max
{
dp[w1, w2], <- we already have the best choice for this pair
dp[w1 - a[i].weight, w2] + a[i].gain <- put in knapsack 1
dp[w1, w2 - a[i].weight] + a[i].gain <- put in knapsack 2
}
时间复杂度为O(n * maxW1 * maxW2)，其中maxW背包的最大重量。请注意，如果容量很大，这不是很有效。
602392714
清零编程群