检测一个整数是否可以表示为给定整数的乘积

Question

我有一组给定的整数：

A[] = { 2, 3, 4, 5, 6, 7, 8, 10, 15, 20, 25, 30, 40, 50, 100, 500 }

1. 我想要检查给定的整数T是否可以被A []中的数字的倍数表示； 编辑澄清： A[]中的任何数字都可以使用。如果使用了，只能使用一次。 例如60是有效的T。60=30*2。 另外90也是有效的。90=3*5*6。

2. 检查哪些数字可以组成该整数T。

3. 如果数字T不能被这些数字的倍数表示，则返回给定T的两个最接近的整数（可以用这种方式写）。

如果有人能帮忙第1部分，我认为我自己可以解决第2部分和第3部分。

我知道这是一个算法问题，甚至是一个数学问题，但如果有人能帮忙，请务必联系我。

不是家庭作业。请看下面的评论。

#

解决方案。 非常感谢所有答案。特别感谢一个答案（但作者选择删除它，我真的不知道为什么，因为它是正确的）。 感谢作者（不记得你的名字了）。

#

带有变化的解决方案代码（作者的算法多次使用了一个乘数。这个算法只使用了一个乘数）

int oldT = 0;
        HashMap<Integer, Boolean> used = new HashMap<Integer, Boolean>();
        while (T != 1 && T != -1) {
            oldT = T;
            for (int multiple : A) {
                if (!used.containsKey(multiple)) {
                    if (T % multiple == 0) {
                        T = T / multiple;
                        used.put(multiple, true); 
                    }
                }
            }
            if (oldT == T)
                return false;
        }
        return true;

- weakwire

---

这似乎是引用了一个作业问题...如果是，请标记“作业”。 - Jason S

不，这不是一个作业问题。我正在开发一款自己的“投注”安卓程序，唯一允许的赌注是这些数字的倍数*0.3（欧元）。 所以这不是作业，而是我正在开发的一个程序功能。 - weakwire

“给定整数的倍数”是什么意思并不清楚。T应该是一些“A[]”的乘积吗？数字可以重复使用吗？或者它是乘积的总和吗？例如，700 = 500 + 2 * 100。 - Stephen C

A 可以有多大？如果不是很大，您可以计算它的所有子集并将它们相乘，以获取所有可能的“赌注”列表，然后在其中执行二进制搜索。 - Walter Mundt

他删除了自己的解决方案，因为它不能处理一些例子，例如A = [2, 6]和T = 6。你首先要将T除以2，得到3，然后就卡住了。可悲的是，暴力解决方案有时会失败 :) - Nikita Rybak

我认为他想说的是“产品”，并且A的每个元素最多只能使用一次。 - Svante

Answer 1

如果T不是非常大（比如小于10的7次方），那么这就是标准DP。

a[1] = true; // means that number '1' can be achieved with no multipliers
for (every multiplier x) {
   for (int i = T; i > 0; --i) {
      if (a[i] and (i * x <= T)) {
          // if 'i' can be achieved and 'x' is a valid multiplier,
          // then 'i * x' can be achieved too
          a[i * x] = true;
      }
   }
}

假设每个乘数只能使用一次。
现在，如果您有另一个数组b[i]，存储用于实现i的乘数，则可以找到T的分解。
如果您时间有限，可以查阅大量在线内容以熟悉动态规划，这应该能帮助您解决此类问题。例如，这个看起来不错
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

- Nikita Rybak

---

不是每个乘数都必须使用。这是我找不到解决方案的棘手问题。它可以是2或3等。此外，T代表“钱”，所以是<<<10^7。感谢链接，我会尝试一下。 - weakwire

不是每个乘数都必须要使用。没错，如果有效的乘数是2和3，则'a'将在1、2、3和6处为'true'。 - Nikita Rybak

还要注意，链接中的第一个问题非常相似：它只是使用加法而不是乘法。 - Nikita Rybak

使用动态规划的想法是不错的，但这并不是一个非常高效的实现。我猜这留给读者去填补。(例如，存储“到目前为止最大的真值”，从不从T/x以上开始，因为那样无论如何都不会通过条件等等...) - Rex Kerr

Answer 2

我不确定你具体在问什么。

如果用户可以选择 n*(其中一个数字)，那么请注意，2、3、5和7是质数，因此如果您的数字可被2、3、5或7整除，则将其除以该数，然后您就有了n*(那个数字)。

如果您必须将数字相乘，但可以多次这样做，请再次注意所有数字都可以分解为2、3、5和7的幂。检查下注是否仅被这些数字整除（除尽直到不能除为止，然后看是否剩下1），并计算每个数字除的次数。

如果您必须将数字相乘而且不能重复使用，则再次找到质因数分解，并从列表中删除使幂出现最平均的数字。如果您设法删除所有倍数，则完成。

在除了最后一种情况之外，可以下注的数字非常密集，因此您可以通过向上或向下移动并重新检查来找到最近的数字。 在最后一种情况下，搜索附近的内容可能有点棘手；您可能只想形成一个可能的（低）赌注表，并从中建议一些内容，假设用户不会下注2 * 3 * 4 * 5 * 6 * 7 * 8 * 10 * 15 * ....

- Rex Kerr

---

直接使用“将它们全部除以T”策略行不通。如果你只有2和6这两个乘数，而T=6，那么你首先会将T除以2，得到3，然后就卡住了。 - Nikita Rybak

是的，我考虑过为所有可能的投注预先形成一个排序表，但是大小会很大（针对移动设备而言）。 非常感谢您的建议。 - weakwire

@Nikita - 这就是我说“选择使幂函数最均匀的数字”的原因。这是一种启发式方法，通常会起作用；对于任意一组数字来说并不总是有效，但对于给定的集合来说效果相当不错。 - Rex Kerr

@weakwire - 这个表并不是很大——你在16个项目中有是或否的答案，这是2^16个条目。如果你放弃那些不可能的大项，表就更小了。这与Nikita建议的策略相同，只是计算效率更高，因为你保证可以在162^16步内找到每个解，而在Nikita的方法中，你需要16T步，其中T是你的上限。 - Rex Kerr