2个容量相同的背包-为什么我们不能两次找到最大值 [英] 2 knapsacks with same capacity - Why can't we just find the max-value twice

问题描述

如果为您提供了一组具有以下值和权重的项目：[[w1，v2），（w2，v2），...（wn，vn）]，以及两个容量为C的背包Knap1和Knap2，目的是确定分别可以进入Knap1和Knap2并最大化背包价值和容量的S1和S2的最佳子集。

If you are given one set of items with values and weight: [(w1,v2),(w2,v2),...(wn,vn)], and two knapsacks Knap1 and Knap2 of equal capacity C, the goal is to determine what are the optimal subsets of items S1 and S2 that can go into Knap1 and Knap2 respectively and maximize the knapsacks' values and capacity.

一种错误的方法解决此问题的方法是，首先使用所有项目作为候选项，用DP编程算法填充Knap1，然后使用Knap1中剩余的项目填充Knap2。

An incorrect way to solve this would be to first fill Knap1 with a DP programming algorithm using all of the items as candidates, and then fill Knap2 by using the leftover items from Knap1.

I不明白如果两个背包的容量相等，为什么此算法不正确。

I don't understand why this algorithm is incorrect if the two knapsacks have equal capacity. Could someone please explain or give an example?

推荐答案

假设背包的容量为10，我们有这些物体（重量，值）：

Suppose the capacity of the knapsacks is 10, and we have these objects (weight, value):

（8，200）
（1，10）
（1，10）
（2，15 ）
（9，100）

(8, 200) (1, 10) (1, 10) (2, 15) (9, 100)

只看一个背包的贪心算法会使用权重8、1和1的对象获得220的值，但是当您认为两个麻袋都明显离开1并取2更好时。

The greedy algorithm only looking at one knapsack would use the objects of weight 8, 1 and 1 to score 220 value, but when you consider both sacks clearly leaving the 1's and taking the 2 is better.

这篇关于2个容量相同的背包-为什么我们不能两次找到最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！