如何把cd里的音频弄出来:把最有价值的物品放在盒子里

我正在做一个编程练习,如下所示:
有一个盒子和一个物品列表。
盒子有固定的大小。每个物品都有自己的大小和价格。
如果物品的大小总和小于盒子的大小,我们可以在盒子中放入任意数量的物品。(每个物品只能放一次)。
找到可以放入价格最高的盒子中的物品组合。

box: size = 10
| item | size | price |
| ---- | ---- | ----- |
| 1    | 8    | 4     |
| 2    | 10   | 5     |
| 3    | 1    | 2     |

在这种情况下,答案将是 6,因为选择了项目 1 和 3,价格 4 + 2 = 6(尺寸总和为 8,低于 10)

我的方法是执行回溯以查找所有可能的组合并记录最高价格,但我不确定如果列表中有大量项目是否足够有效。

有没有更有效的方法?

1

是的,有一种方法更有效!

动态编程-自下而上

方法:不是通过评估所有可能的子集来强制求解,而是可以针对每个权重的每个项目迭代地解决问题。以这个例子为例:
假设有四个项目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)

1

这正是0/1 knapsack problem。实际上,尝试所有组合都可以解决问题,但是对于超过 50 个项目来说,这将花费不可能的时间。

问题是NP-完全的,但是可以通过伪多项式求解。也就是说,如果框的总大小相对较小,则可以有效地解决。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处

(651)
Excle表格:TricentisToscaExcle按钮在错误的地方
上一篇
Decoded:PDF 1.6交叉引用流解码(decoded pdf)
下一篇

相关推荐

  • cv小敢:如何利用CV小敢提升职业技能?

    cv小敢(Computer Vision Tiny-YOLO)是一种轻量级的物体检测算法,它可以在资源受限的设备上运行,如嵌入式设备、智能手机等。它是基于YOLO(You Only Look Once)算法的一个变体,由Joseph Redmon和Ali Farhadi开发,旨在提高深度学习模型的性能,同时减少模型的大小和计算复杂度。…

    2023-02-09 13:08:59
    0 40 67
  • cviu期刊:基于深度学习的图像复原算法研究

    Computer Vision and Image Understanding(CVIU)是一本国际学术期刊,专注于计算机视觉和图像理解的研究。它发表有关计算机视觉、图像处理和图像理解的原创性研究论文,以及有关这些领域的应用。CVIU的目标是推动计算机视觉和图像理解的发展,为读者提供最新的研究成果和思想。…

    2023-02-23 05:50:40
    0 62 22
  • cv领域是什么意思最新的发展趋势与应用

    cv领域是计算机视觉的缩写,是指使用计算机来识别、理解和处理图像信息的领域。它可以帮助计算机“看”到世界,并从图像中提取有用的信息。…

    2023-02-01 02:20:34
    0 67 49
  • cv紫枫儿广播剧一个追求梦想的故事

    cv紫枫儿广播剧是一款由紫枫儿团队开发的虚拟广播剧,它使用虚拟现实技术来创造一个真实的广播剧环境。紫枫儿团队在这款游戏中使用了多种技术,包括3D模型、动画、声音和虚拟现实。玩家可以在这款游戏中体验到真实的广播剧环境,就像自己置身于一个真实的广播剧录制现场。…

    2023-01-30 05:26:44
    0 77 28
  • pvd和cvd的区别比较物理气体化学沉积法的优势与劣势

    PVD(Physical Vapor Deposition)是物理蒸发沉积的缩写,它是一种利用物理方法将源材料从固体直接转化为气态,然后在被涂层表面形成薄膜的技术。CVD(Chemical Vapor Deposition)是化学蒸发沉积的缩写,它是一种利用化学反应将源材料从气态直接转化为固态,然后在被涂层表面形成薄膜的技术。…

    2023-02-27 02:45:17
    0 11 81
  • cookie路径:如何使用Cookie路径来提升网站安全性?

    示例示例Cookie路径是一个可选的属性,用于指定可以访问cookie的URL路径。如果未指定,则默认为当前文档位置的路径。例如,如果你想让cookie可以被www.example.com/foo/bar.html访问,你可以使用下面的代码:…

    2023-03-18 15:31:32
    0 16 15
  • cvc留置时间:观察CVC留置时间的影响

    CVC留置时间是指在支付过程中,银行将支付金额暂时留存在客户账户中的一段时间。这段时间可以是几分钟,也可以是几天,具体取决于银行的政策。…

    2023-02-17 08:13:51
    0 71 97
  • cookie的特点:如何利用Cookie提升网站用户体验

    示例示例Cookie的特点:Cookie是一种小型文本文件,由Web服务器存储在用户计算机中的特殊文件夹中,每当用户浏览器向服务器发送请求时,它会附带cookie信息。…

    2023-03-09 02:59:37
    0 35 12

发表评论

登录 后才能评论

评论列表(76条)