如何把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-完全的,但是可以通过伪多项式求解。也就是说,如果框的总大小相对较小,则可以有效地解决。

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

(357)
奔驰c级中网改装:使用网络信息的 C# 中网络电缆的状态
上一篇
操作代码:创建具有操作功能的“面”代码(happy face codehs)
下一篇

相关推荐

  • docker游戏服务器:如何使用Docker搭建高性能的游戏服务器

    Docker游戏服务器是一种将游戏服务器部署到容器中的方式,它可以帮助游戏开发者快速、轻松地部署游戏服务器,并且可以更轻松地扩展游戏服务器的容量。…

    2023-04-27 09:55:33
    0 45 26
  • win7玩cf卡顿怎么解决:解决Win7环境下CF游戏卡顿问题

    尝试更新系统:可能是由于系统缺少某些补丁或者更新导致CF卡顿,可以尝试在Windows Update中进行检查更新,并安装最新的补丁和更新。更新显卡驱动:可能是由于显卡驱动过旧或者不兼容导致CF卡顿,可以尝试更新显卡驱动,可以到显卡厂商官网下载最新的驱动进行安装。…

    2023-05-27 11:45:17
    0 97 60
  • cv糖醋排骨是弯的吗弯曲的美味

    cv糖醋排骨不是弯的,它是一种制作方法,通常用来制作排骨。代码:…

    2023-04-01 13:03:36
    0 79 75
  • java ee eclipse使用:如何使用Java EE Eclipse来开发Web应用

    示例示例Java EE Eclipse使用步骤:安装Eclipse IDE。…

    2023-10-12 04:51:32
    0 89 53
  • cookie如何使用:如何使用Cookie来改善用户体验

    Cookie是一种存储在客户端的小型文件,用于记录用户的信息,如访问时间、登录状态等。使用Cookie可以更好地为用户提供服务,比如保存用户的登录状态,记录用户的浏览历史记录等。…

    2023-05-07 02:18:11
    0 66 71
  • cv小敢:如何利用CV小敢提升职业技能?

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

    2023-02-09 13:08:59
    0 71 35
  • ubuntu如何编译c语言:在Ubuntu上编译C语言程序的步骤

    示例示例Ubuntu编译C语言的步骤如下:安装gcc编译器:…

    2023-09-08 12:39:20
    0 25 17
  • coremail论客邮箱Coremail论客邮箱

    Coremail论客邮箱是一款专业的企业邮箱服务,可以满足企业对安全、可靠性和高效性的要求。它拥有强大的安全性能,可以提供多种安全保护,包括防止邮件被窃取、拦截恶意邮件、防止跨站脚本攻击等。此外,它还支持多种企业级功能,如组织架构管理、收发邮件管理、文件共享管理、联系人管理等,可以帮助企业提高工作效率,提升企业形象。…

    2023-02-25 04:36:55
    0 57 75

发表评论

登录 后才能评论

评论列表(10条)