使阵列值的总和等于k-编程知识-白鹭情

我遇到了一个算法问题，我不知道如何原则上解决它，因为我没有找到任何可以在这里使用的算法。也许有人可以帮助我。

任务：有一个拉丁字符阵列。阵列中的每个字符都可以替换为任意整数。替换后，所有相同的字符也将替换为相同的数字。有没有可能让阵列值的总和等于k？

输入：

array - 拉丁字符阵列，0<length(array)<20, sub_array[i]="x" | "是" | “z”
k - 要得到的阵列之和的值，0<k<150

输出：布林值——可以或不能使阵列阵列的值之和等于k

示例（飞镖）：

var array = ["x", "x", "x", "y", "z"];
var k = 10;
print(getResult(array, k)); // return true, because [2, 2, 2, 3, 1]

uj5u.com热心网友回复：

观察：给定nx、my 等，通过将 x、y、... 值中的任何一个更改 1，总和只能以 GCD(n, m, ...) 为增量更改，其中 GCD 是最大公约数（可以用欧几里得算法找到）。

k因此，只有当是其数量 GCD 的倍数时，才能满足条件。

注意：这假设 x, y, ... 可能不是唯一的，并且可能是负数

uj5u.com热心网友回复：

首先，您可以遍历阵列并计算“x”、“y”和“z”的出现次数。我将这些计数称为 x、y 和 z。那么问题就变成了：

你能找到整数 a、b 和 c，使得 a * x b * y c * z = k。

如果数字可以是负数，那么它相对简单：如果 k % gcd(x, y, z) = 0 是可能的（忽略 0，所以如果 x 为 0 则 k % gcd(y, z) = 0）。换句话说，只有当你可以制作 gcd(x, y, z) 的倍数并且 k 不是这些数字的倍数时，才有可能失败。

如果 a、b 和 c 必须是非负数，那么它会变得有点复杂。我们正在处理货币 x、y 和 z 的硬币问题。如果 k % gcd(x, y, z) != 0 则永远不可能。现在我们可以通过将 k, x, y 和 z 除以 gcd(x, y, z) 来简化问题。之后，我们可以通过使用 Frobenius 数来查看是否可以轻松实作：

n = 2：所有数字 > x * y - x - y 都可以构建

n = 3：可以构建所有数字 > sqrt(3 * x * y * z)

如果 k 小于该值，我们可以检查是否可以使用硬币问题的常见动态规划解决方案来构建 k。

当然，您必须处理一些边缘情况。例如 k = 0 或者如果只给出一个数字，那么它就是 k % x = 0。

uj5u.com热心网友回复：

这是一个简单的解决方案，它适用于以下假设：

一个数字最多可以分配给一个字符
至少有一个字符只出现一次

function findNumbers([s,sum]) {   // count occurences of characters:
  let ar1 = Object.entries(s.split("").reduce((a, c) => (a[c] = (a[c] || 0)   1, a), {}))
   .sort((a, b) => b[1] - a[1]); // sort: most frequent characters first
  
  // assign interger values to each character (starting with 1 ...
  let ar2=ar1.map(([c, n], i) =>{ // c: character, n: occurences, i: index
    sum-=n*(i 1);
    return [c, i 1<ar1.length? i 1: ar1.length sum]
   });
  return [Object.fromEntries(ar2),ar2.pop()[1]>ar2.pop()[1]]; // add a results flag to each solution: true/false
}

let res=[["xxxyz",10],["ghijjk",17],["abcabcabd",12],["abccdef",18],["abcd",9]].map(findNumbers)

console.log(res)  // true, true, false, false, false