我试图解决以下问题,并想知道是否存在任何适合解决此问题的背包算法的变化

问题:

一个小偷进入房子的意图是,偷东西 . 他需要x Kg的银,y Kg的金和z Kg的钻石 . 房子里有许多由金,银和钻石制成的物品 . 每个项目可以包含任何数量的这些元素(即,它可以是纯金,或金和银的合金,或金和钻石的合金等) . 每个商品都附有价格标签 . 现在,我们的小偷是一个正直的男人,他不希望主人受到太大的伤害,所以他决定偷走这些东西,以至于包里所有东西的总成本是最不可能的 . 保存在那里的物品有多个副本,因此他可以多次将同一物品放在包里 . 他不介意他保留在包里的数量是否多于要求(X Kg,Y Kg,Z Kg),因为要求无法以较低成本的方式完成 .

根据我的搜索结果,我找不到任何处理这种情况的背包变体 . 如果有其他方法可以解决这个问题,请随时告诉我,我不是在看 .

EDIT

我尝试过的一种方法是找到满足需求的项目的所有可能组合,然后迭代它们以找到价格最低的组合 . 但是,一旦组合开始变大,这种方法非常无效

EDIT 2 我正在补充一个澄清的例子;

说,有5个项目avaialble

材料|金|银|钻石|价格Item1 | 2 | 3 | 4 | 2000 Item2 | 4 | 3 | 2 | 1600 Item3 | 0 | 3 | 0 | 200 Item4 | 20 | 0 | 10 | 5000 Item5 | 15 | 15 | 0 | 5500

小偷想要10公斤的金,银和钻石

他可以选择(Item4 Item5)或(3X Item2 Item1)来满足他的需要,但他会选择后者选项,因为它的价格为6800,而第一个的价格为10500 .

现在,为了得到这个结果,小偷认为这些项目的每一个组合都是可能的,然后选择价格最低的组合,但正如我之前提到的那样,这不是最好的方法 . 这可以通过任何贪心算法以某种方式解决吗?