algorithm - 将数字转换为特殊的基本系统

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。

保证给定的数字可以转换到这个专门的基础系统。

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

Answer 1

简而言之，将每个基数(在您的示例中为 2^2、3^1、2^0)视为元素的重量，将整数视为袋子的容量。这个问题要我们找到这些元素的组合，它们正好装满袋子。

首先，这个问题是 NP 完全问题。它与 subset sum problem 相同，也可以看作是 knapsack problem 的导数问题.

尽管如此，这个问题仍然可以通过使用动态规划的伪多项式时间算法在 O(nW) 时间内解决，其中 n 是基数，W 是要分解的数。可以在这个维基百科页面中找到详细信息:http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming和这个 SO 页面:What's it called when I want to choose items to fill container as full as possible - and what algorithm should I use? .