时间戳

首页 > 解决方案 > 寻找最接近目标的数组值总和的逻辑

javascript - 寻找最接近目标的数组值总和的逻辑

问题描述

这是一个更简单的背包版本，我很难把头包起来。

在我的版本中，我不在乎物品的价值。我只是想尽可能地接近承重能力，顺序并不重要，因为我要多次这样做，并且在两者之间改组。

所以要清楚：我有一个值数组，例如：weights = [{44, 52, 100, 33, 33, 22, 25, 4, 6, 77, 88, 45}]和容量，例如：capacity: 204

我想要最接近该容量数字的数组值组合而不重复任何内容，我的数学不是超级好，维基百科的文章完全让我迷失了方向。

有人可以解释如何得到这个吗？

标签： javascriptalgorithmlogicdynamic-programmingknapsack-problem

解决方案

朴素的方法：循环遍历 N 个数字的所有子集，并检查权重的总和。运行时间为 O(2^N*N)

你可以试试动态规划。该问题可以分为2个子问题，检查集合的总和是否等于或小于容量。1）将当前元素包含在子集中，并以剩余总和重复剩余项目。2）从子集中排除当前元素，重复剩余项目。递归的基本情况是没有剩余项目。最后，我们输出子集中包含的项目。运行时间为 O(n*capacity) in O(n)

推荐阅读