时间戳

首页 > 解决方案 > 如果身体可以的话，我该如何解决带有负面物品的背包问题？

algorithm - 如果身体可以的话，我该如何解决带有负面物品的背包问题？

问题描述

我有一个类似于背包但有两个小区别的程序的问题。

项目的第一个值可以是负数。

其次，如果背包中有物品的空间，即使它降低了背包的当前价值，它也必须这样做。

常见的方法没有帮助，因为如果我的物品是

Weigh Value

1 100

2 1

1 -1000

背包容量为2，每件物品可放入背包一次

第一项将插入

0 to backpack of 0

100 to backpack of 1 

100 to backpack of 2

到目前为止一切都很好，但第二件物品永远不会进入，因为它的价值低于第一件，第三件毁了一切，因为 1 的背包将是相同的，但这个可怕的物品适合 2 的背包并且价值降低到 -900，因为我可以当我可以很好地处理第二项并且值为 1 时，不要跳过它。

关键是插入看起来更糟糕但占用更多空间的项目，这样最糟糕的项目就无法进入。

不幸的是，如果项目如下：

Weigh Value

1 100

2 1

1 -10

那么带第一个和第三个项目的背包比带第二个项目的背包要好，所以我不能无脑地用任何正面价值的物品装满我的背包来否认负面的物品，因为有时（上面的例子）不是答案。

我没主意了。

标签： algorithmknapsack-problem

解决方案

推荐阅读