Lar*_*Dev 6 javascript algorithm math dynamic-programming subset-sum
所以，我有这个问题需要解决，显然这被称为Subset Sum Problem，除了我不仅需要在精确到给定数字时获得子集，而且在没有精确和达到给定数字的情况下最接近数字，它不应该超过参考数字，只在下面，如果有两个以上可能的子集具有相同的结果，我想得到分布更好的子集，从最高到最低的数字数组作为首选，并限制每个子集不超过相同数量的 10 次，允许重复，例如：
这是具有预定义值的数组：
let num = [64.20, 107, 535, 1070];
和一个给定的数字：
let investment = 806.45
一种可能的解决方案是：
[0, 2, 1, 0] // this sums up to 749 (since there is no way to get to 806.45 with the given array)
请注意，此结果是指 nums 中的每个值允许达到总和的次数：
但更好的解决方案是：
[4, 5, 0, 0] // this sums up to 791.80 (since there is no way to get to 806.45 with the given array)
还有一个更好的解决方案（因为首先考虑较高的值而不是较低的值）
[4, 0, 1, 0] // this sums up to 791.80 also but you can see it's taking a higher value when possible.
另一个重要的限制是永远不应该给出负面结果。
到目前为止，我已经尝试过这样（在 VueJS 中）：
getPackages(){
let investment = 806.45;
const num = [64.20, 107, 535, 1070]
let a, b, c, d;
let results = [];
a = investment / num[0] >= 0 ? (investment/num[0]) : 0;
b = investment / num[1] >= 0 ? (investment/num[1]) : 0;
c = investment / num[2] >= 0 ? (investment/num[2]) : 0;
d = investment / num[3] >= 0 ? (investment/num[3]) : 0;
let dResult = [], cResult = [], bResult = [], aResult = [];
for (let i = 0; i <= d; i++){
if (i>0){
dResult.push((i * num[3]))
}
}
for (let i = 0; i <= c; i++){
if (i>0){
cResult.push((i * num[2]))
}
}
for (let i = 0; i <= b; i++){
if (i>0){
bResult.push((i * num[1]))
}
}
for (let i = 0; i <= a; i++){
if (i>0){
aResult.push((i * num[0]))
}
}
let aResultCoincidences = [];
let bResultCoincidences = [];
let cResultCoincidences = [];
let dResultCoincidences = [];
bResult.forEach(value => {
aResult.findIndex(item => item === value) > 0 ? bResultCoincidences.push(aResult.findIndex(item => item === value)) : null
})
aResult.splice(0, Math.max(...bResultCoincidences) + 1)
cResult.forEach(value => {
bResult.findIndex(item => item === value) > 0 ? cResultCoincidences.push(bResult.findIndex(item => item === value)) : null
})
bResult.splice(0, Math.max(...cResultCoincidences) + 1)
dResult.forEach(value => {
cResult.findIndex(item => item === value) > 0 ? dResultCoincidences.push(cResult.findIndex(item => item === value)) : null
})
cResult.splice(0, Math.max(...dResultCoincidences) + 1)
this.package1 = aResult.length
this.package2 = bResult.length
this.package3 = cResult.length
this.package4 = dResult.length
},
在我的方法中发生的事情是，我尝试从每次乘法中获得所有可能的结果，然后我删除我用这种组合制作的数组之间匹配的那些，最终得到结果，但这没有得到很好的优化，我肯定有可能有更好的解决方案来解决这个问题。
无论如何忽略 vuejs 实现，这只是在 DOM 中设置值。
*** ES6 解决方案会很棒。
可以玩的CodeSandbox：CODESANDBOX LINK
提前致谢。
这是一种方法。我没有仔细查看你的，不知道这是否比它有任何优势。
\n这是一种蛮力方法，只需对每个类别的潜在单个值进行叉积，对总数进行求和，然后缩小列表以找到最接近目标的所有选项。我最初的写法略有不同，试图捕获最接近的值，无论是高于还是低于目标。
\n这是带有几个辅助函数的实现：
\nconst sum = (ns) =>\n ns .reduce ((a, b) => a + b, 0)\n\nconst crossproduct = (xss) => \n xss.reduce((xs, ys) => xs.flatMap(x => ys.map(y => [...x, y])), [[]])\n\nconst range = (lo, hi) =>\n [...Array(hi - lo)] .map ((_, i) => lo + i)\n\nconst call = (fn, ...args) => \n fn (...args)\n\nconst closestSums = (t, ns) => \n call (\n (opts = crossproduct (ns .map (n => range (0, 1 + Math .ceil (t / n))))) => \n opts .map (xs => [xs, sum (xs .map ((x, i) => x * ns [i]))])\n .reduce (\n ({best, opts}, [opt, tot]) => \n call (\n (diff = t - tot) => \n diff >= 0 && diff < best\n ? {best: diff, opts: [opt]}\n : diff >= 0 && diff == best\n ? {best, opts: [...opts, opt]}\n : {best, opts}\n ),\n {best: Infinity, opts: []}\n ) .opts\n )\n\nconst byHigher = (as, bs) =>\n as .reduceRight ((r, _, i) => r || (as[i] < bs[i] ? 1 : as[i] > bs[i] ? -1 : 0), 0)\n\nconst closestCounts = (t, ns) => \n closestSums (t * 100, ns .map (n => 100 * n)) \n .filter (cs => cs.every(c => c <= 10))\n .sort (byHigher)\n\nconsole .log (\n closestCounts (806.45, [64.20, 107, 535, 1070]),\n closestCounts (791.8, [64.20, 107, 535, 1070]) // exact match\n).as-console-wrapper {max-height: 100% !important; top: 0}请注意，包装器将所有内容乘以 100，以消除小数和潜在的浮点舍入错误。如果这不起作用，那么添加一些匹配容差就很容易了。
\n最终排序为 na\xc3\xafve，假设您的值按升序排列。如果不是，该分拣机就必须变得更加复杂。
\n正如我所说，这不太可能有效，并且可能不会在您的版本上获得任何好处，但它至少是一种不同的方法。
\n