检测是否可以将整数写为给定整数的乘法

Question

我有一组给定的整数:

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

1. 我想检查给定的整数是否T可以写为数字的倍数A[]; EDIT澄清:任何数量的在A [] 可以使用仅可使用一次是used.If.EX 60是有效的T.60 = 30*2.AlSO 90有效.90 = 3*5*6

2. 检查哪些数字可以形成整数T.

3. 如果数字不能写为该数字的倍数,也会返回给定的2个最接近的整数T(可以这样写)T.

第2部分和第3部分,如果有人帮助我完成第1部分,我想我可以自己解决.

我知道这是一个算法问题,甚至是数学问题,但如果有人可以提供帮助,请做.

不是家庭作业.见下面的评论.

#

解.非常适合所有答案.1回答特别(但作者选择删除它,我不知道为什么,因为它是正确的.)Ty作者(不记得你的名字.)

#

带有扭曲的解决方案代码(作者的算法多次使用一次乘法器.这个只使用乘法器1次)

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;

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