将一个数字转换成一个特殊的基本系统

Question

我想把基数10中的数字转换成一个特殊的基形式，如下所示：

A*2^2 + B*3^1 + C*2^0

A可以接受0,1的值。

B可以取0,1,2的值

C可以接受0,1的值。

例如，数字8应该是

1*2^2 + 1*3 + 1。

保证给定的号码可以转换成这个专门的基本系统。

我知道如何从这个基础系统转换回基础-10，但我不知道如何转换从基础-10到这个专门的基础系统。

Answer 1

简而言之，将每个基数(示例中的2^2、3^1、2^0 )当作一个项目的重量，将整个数字作为一个袋子的容量。这个问题想让我们找出这些物品的组合，它们准确地填满了袋子。

首先，这个问题是NP-完全的。它与子集和问题完全相同，也可以看作是背包问题的一个导数问题。

尽管如此，这个问题仍然可以用O(nW)时间中使用动态规划的伪多项式时间算法来解决，其中n是基数，W是要分解的数。详细信息可以在维基百科的页面：编程和这个SO页面：当我想要选择尽可能装满容器的项目时，它被称为什么?我应该使用什么算法？中找到。

Answer 2

简化你的“特别基础”：

X = A * 4 + B * 3 + C
A E {0,1}
B E {0,1,2}
C E {0,1}

显然，可以表示的最大数字是4 + 2 * 3 + 1 = 11。

要想知道如何得到A、B、C的值，您可以做两件事中的一件：

1. 只有12个可能的输入:创建一个查找表。丑陋但很快。
2. 使用一些算法。有点棘手。

让我们先来看看(1)：

A B C X 0 0 0 1 0 1 0 1 4 0 2 0 0 2 1 7 1 0 0 4 1 0 1 1 5 1 1 0 7 1 1 1 8 1 2 0 10 1 1 11

请注意，2和9不能在此系统中表示，而4和7则发生两次。对于给定的输入，您有多个可能的解决方案，这意味着没有一个真正健壮的算法(除了查找表)来实现您想要的结果。所以你的桌子可能是这样的：

int A[] = {0,0,-1,0,0,1,0,1,1,-1,1,1};
int B[] = {0,0,-1,1,1,0,2,1,1,-1,2,2};
int C[] = {0,1,-1,0,2,1,0,1,1,-1,0,1};

然后查找A，B，C。如果A<0时，就没有解了。