我正在做一个编程练习,如下所示:
有一个盒子和一个物品列表。
盒子有固定的大小。每个物品都有自己的大小和价格。
如果物品的大小总和小于盒子的大小,我们可以在盒子中放入任意数量的物品。(每个物品只能放一次)。
找到可以放入价格最高的盒子中的物品组合。
box: size = 10
| item | size | price |
| ---- | ---- | ----- |
| 1 | 8 | 4 |
| 2 | 10 | 5 |
| 3 | 1 | 2 |
在这种情况下,答案将是 6,因为选择了项目 1 和 3,价格 4 + 2 = 6(尺寸总和为 8,低于 10)
我的方法是执行回溯以查找所有可能的组合并记录最高价格,但我不确定如果列表中有大量项目是否足够有效。
有没有更有效的方法?
是的,有一种方法更有效!
动态编程-自下而上
方法:不是通过评估所有可能的子集来强制求解,而是可以针对每个权重的每个项目迭代地解决问题。以这个例子为例:
假设有四个项目i[1,2,3,4]
,它们具有关联的权重w[5,3,4,2]
,值v[60,50,70,30]
和最大权重w = 5
。
现在,我们将构造一个 2D 值数组,该数组在选择某个项目具有一定权重V[i][w]
时保存最大值。
填充数组的算法是:
V[i][w] = max(V[i-1,w],V[i-1,w-w_i] + v_i) OTHERWISE V[i-1,w]
这是什么?:
对于每个重量下的每个项目,如果我们甚至可以在不超过重量限制的情况下选择项目,我们首先看。如果没有,我们将在该重量下采用上述项目的值(如果该项目也无法选择,则为 0)。
如果我们可以选择项目,那么有趣的事情就会发生。如果是这样,如果选择的项目大于如果选择上面的项目的值,我们将选择当前项目:(So if V[i-1, w] < V[i-1, w - w_i] + v_i)
对所有 n 个项目和 w 个权重执行此操作,您将获得最高的可能值。在上述示例中执行算法时,这将是 Matrix:
现在要解决背包问题,我们从 w = 5 的第 2 列中选择项目的值。我们看到选择项目 4 最终产生了最大值。我们还可以看到该值的来源。如果我们选择项目 4,从权重中减去 2,然后我们在 w = 3 的列中选择一行,因为我们选择了项目 4,无法再次选择它。然后我们查看了项目 3,但是如果我们减去 w =3
与蛮力方法的O(2 ^ N)相比,运行它的复杂性是O(N * W)。
这正是0/1 knapsack problem。实际上,尝试所有组合都可以解决问题,但是对于超过 50 个项目来说,这将花费不可能的时间。
问题是NP-完全的,但是可以通过伪多项式求解。也就是说,如果框的总大小相对较小,则可以有效地解决。
本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处
评论列表(10条)