java中背包的贪婪算法

-1

我想为背包问题编写一个非常简单的贪婪算法。我的输入是两个平行的数组。一个数组包含项目的值，另一个数组包含权重。java中背包的贪婪算法

我试图写的贪婪算法如下：检查哪个项目具有最高值并将其放入背包中。然后将此项目的值设置为零。如果背包仍然可以拿着它，再次检查哪个物品具有最高价值并将其放入背包中。如果它可以保持它，请将该值再次设置为零（放入后），然后再次开始查找最高值。如果那个背包不能拿住它，那么就结束这个程序。

我知道有很多更好的贪婪算法，但在我看来这是一个非常简单的算法，我想我可以管理它。我的问题是，我必须通过整个值数组来找到最大值。然后，当我找到它时，我把它放在背包里，并将其值设为零。但问题是我必须回到for循环才能找到新的最高价值物品并将其放入背包中。但我不知道如何去做这件事。

我正在用Java写这篇文章。

来源

2016-06-29 Tezen

首先，你通常用贪婪的方式解决背包问题，即通过使用最高的比率值/重量而不是价值。

其次，如果您对项目列表进行一次排序并逐步浏览，则无需在每个步骤中搜索最大值。

来源

2016-06-29 11:16:50

谢谢你的回应。我知道有很多方法可以使用贪婪算法来解决背包问题，并且我已经看到并使用了具有最高比例的值/权重的方法。我只是想尝试各种不同的编程练习，因为我是一个绝对的初学者。首先对它们进行排序然后重复遍历它们的问题是我的体重指数不再对应我的价值指数，因此我无法再检查它是否仍然适合背包。我认为我要这样做的方式可能是解决这个问题的一种解决方法。 – Tezen

权重和值之间存在对应关系（即它们不能任意重新排列）。目前，这听起来像是将权重和值存储在单独的数组中，并试图纯粹由数组的顺序来强制执行。您可以通过创建一个包含项目的值/重量的简单类来封装该信息，然后可以创建并排序这些对象的数组，而无需手动跟踪哪个权重和值属于一起。 –

java中背包的贪婪算法

回答

相关问题