具有 k 个 1 位的最小 n 位整数 c 是两个 g、h 位设置为 1 的 n 位整数之和（动态规划）

Question

我正在尝试解决以下问题：

Find the smallest n-bit integer c that has k 1-bits and is the sum of two n-bit integers that have g, h bits set to 1. g, h, k <= n

首先，这里的n位整数意味着我们可以使用所有n位，即最大。这样一个整数的值是2^n - 1。所描述的整数可能根本不存在。很明显，k > g + h 的情况没有解决方案，对于 g + h = k，答案只是 2^k - 1（第一个 k 位是 1 位，k - n 个零正面）。

关于程序应该做什么的一些例子：

g = h = k = 4, n = 10 :
0000001111 + 0000001111 = 0000011110
15 + 15 = 30 (30 should be the output)


(4, 6, 5, 10):
0000011110 + 0000111111 = 0001011101
30 + 63 = 93

(30, 1, 1, 31):
1 + (2^30 - 1) = 2^30

据我所知，这是一个动态规划问题，我选择了以下方法：设dp[g][h][k][n][c]为描述的整数，c为可选的进位位。我尝试根据最低位重建可能的总和。所以，dp[g][h][k][n + 1][0] 是

的最小值

(0, 0):       dp[g][h][k][n][0]
(0, 0): 2^n + dp[g][h][k - 1][n][1]
(1, 0): 2^n + dp[g - 1][h][k - 1][n][0]
(0, 1): 2^n + dp[g][h - 1][k - 1][n][0]

同理，dp[g][h][k][n + 1][1]是

的最小值

(1, 1): dp[g - 1][h - 1][k][n][0]
(1, 1): dp[g - 1][h - 1][k - 1][n][1] + 2^n
(1, 0): dp[g - 1][h][k][n][1]
(0, 1): dp[g][h - 1][k][n][1]

这个想法并不难，但我对这类事情并没有真正的经验，而且我的算法即使对于最简单的情况也不起作用。我选择了自上而下的方法。我很难考虑所有的极端情况。我真的不知道我是否正确选择了递归基础等。我的算法甚至不适用于 g = h = k = 1, n = 2（答案是 01 + 01 = 10）的最基本情况。 g = h = k = 1, n = 1 不应该有答案，但算法给出 1（这基本上就是前一个示例输出 1 而不是 2 的原因）。所以，这是我糟糕的代码（只有非常基本的 C++）：

int solve(int g, int h, int k, int n, int c = 0) {
  if (n <= 0) {
    return 0;
  }
  if (dp[g][h][k][n][c]) {
    return dp[g][h][k][n][c];
  }
  if (!c) {
    if (g + h == k) {
      return dp[g][h][k][n][c] = (1 << k) - 1;
    }
    int min, a1, a2, a3, a4;
    min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
    if (g + h > k && k <= n - 1) {
      a1 = solve(g, h, k, n - 1, 0);
    }
    if (g + h >= k - 1 && k - 1 <= n - 1) {
      a2 = (1 << (n - 1)) + solve(g, h, k - 1, n - 1, 1);
    }
    if (g - 1 + h >= k - 1 && k - 1 <= n - 1) {
      a3 = (1 << (n - 1)) + solve(g - 1, h, k - 1, n - 1, 0);
    }
    if (g + h - 1 >= k - 1 && k - 1 <= n - 1) {
      a4 = (1 << (n - 1)) + solve(g, h - 1, k - 1, n - 1, 0);
    }
    min = std::min({a1, a2, a3, a4});
    return dp[g][h][k][n][c] = min;
  } else {
    int min, a1, a2, a3, a4;
    min = a1 = a2 = a3 = a4 = std::numeric_limits<int>::max();
    if (g - 2 + h >= k && k <= n - 1) {
      a1 = solve(g - 1, h - 1, k, n - 1, 0);
    }
    if (g - 2 + h >= k - 1 && k - 1 <= n - 1) {
      a2 = (1 << (n - 1)) + solve(g - 1, h - 1, k - 1, n - 1, 1);
    }
    if (g - 1 + h >= k && k <= n - 1) {
      a3 = solve(g - 1, h, k, n - 1, 1);
    }
    if (g - 1 + h >= k && k <= n - 1) {
      a4 = solve(g, h - 1, k, n - 1, 1);
    }
    min = std::min({a1, a2, a3, a4});
    return dp[g][h][k][n][c] = min;
  }
}

Answer 1

我不太相信动态规划方法。如果我理解正确，你需要定义如何去 dp[g + 1][h][k][n]、dp[g][h + 1][k][n]、dp[g][h][k + 1][n] 和 dp[g][h][k][n + 1]，有和没有进位，在以前的计算函数中，我不确定所有这些规则的正确规则是什么。

我认为考虑问题的更简单方法是 A* search 树，其中每个节点包含两个要相加的部分候选数字，我们称它们为 G 和 H。您从节点 G 开始= 0 和 H = 0 在水平 m = 0，并按如下方式工作：

如果 G + H 有 n 位或更少位且 k 有 1 位，这就是解决方案，您找到了！
否则，如果
n - m < G + H - k
中 1 的位数丢弃节点（没有可能的解决方案）。
否则，如果
(g + h) - (G 中 1 的位数 + H 中 1 的位数) < k - G + H 中 1 的位数
丢弃节点（不可行的候选者）。
否则，将节点分支到新的级别。通常每个节点最多有四个子节点，分别在 G 和 H 前加上 0 和 0、0 和 1、1 和 0 或 1 和 1。然而：
- 如果 G 中 1 的位数少于 g，则只能在 G 前加上 1，H 和 h 也类似。
- 在级别 m（G 和 H 有 m 位），如果
  ，你只能在 G 前面加一个 0 n - m > g - G
  中 1 的位数对于 H 和 h 也类似。
- 如果 G == H 和 g == h，您可以跳过 0 和 1 以及 1 和 0 之一，因为它们将导致相同的子树。
继续下一个节点并重复，直到找到解决方案或您没有更多节点可访问。

访问节点的顺序很重要。您应该将节点存储在优先级 queue/heap 中，以便下一个节点始终是可能导致最佳解决方案的第一个节点。这其实很简单，你只需要为每个节点取 G + H 并在其前面加上必要数量的 1 位来达到 k；这是最好的解决方案。

可能有更好的规则来丢弃无效节点（步骤 2 和 3），但算法的思想是相同的。

Answer 2

你可以根据位数g、h、k构造最小和，根本不需要做任何动态规划。假设 g ≥ h（否则切换它们）这些是规则：

k≤h≤g

      11111111  <-  g ones  
  111100000111  <-  h-k ones + g-k zeros + k ones
 1000000000110  <-  n must be at least h+g-k+1

h≤k≤g

    1111111111  <-  g ones  
      11111100  <-  h ones + k-h zeros
    1011111011  <-  n must be at least g+1

h≤g≤k

 1111111100000  <-  g ones + k-g ones  
 1100000011111  <-  g+h-k ones, k-h zeros, k-g ones
11011111111111  <-  n must be at least k+1, or k if g+h=k

示例：n=10、g=6 和 h=4 的所有 k 值：

k=1           k=2           k=3           k=4       
0000111111    0000111111    0000111111    0000111111
0111000001    0011000011    0001000111    0000001111
----------    ----------    ----------    ----------
1000000000    0100000010    0010000110    0001001110

k=4           k=5           k=6
0000111111    0000111111    0000111111
0000001111    0000011110    0000111100
----------    ----------    ----------
0001001110    0001011101    0001111011

k=6           k=7           k=8           k=9           k=10
0000111111    0001111110    0011111100    0111111000    1111110000
0000111100    0001110001    0011000011    0100000111    0000001111
----------    ----------    ----------    ----------    ----------
0001111011    0011101111    0110111111    1011111111    1111111111

或者，不先计算a和b，直接求c的值：

k≤h≤g

c = (1 << (g + h - k)) + ((1 << k) - 2)

h≤k≤g

c = (1 << g) + ((1 << k) - 1) - (1 << (k - h))

h≤g≤k

c = ((1 << (k + 1)) - 1) - (1 << ((g - h) + 2 * (k - g)))

h + g = k

c = (1 << k) - 1

这导致了这个令人失望的平凡代码：

int smallest_sum(unsigned n, unsigned g, unsigned h, unsigned k) {
    if (g < h) {unsigned swap = g; g = h; h = swap;}
    if (k == 0) return (g > 0 || h > 0 || n < 1) ? -1 : 0;
    if (h == 0) return (g != k || n < k) ? -1 : (1 << k) - 1;
    if (k <= h) return (n <= h + g - k) ? -1 : (1 << (g + h - k)) + ((1 << k) - 2);
    if (k <= g) return (n <= g) ? -1 : (1 << g) + ((1 << k) - 1) - (1 << (k - h));
    if (k < g + h) return (n <= k) ? -1 : (1 << (k + 1)) - 1 - (1 << (2 * k - g - h));
    if (k == g + h) return (n < k) ? -1 : (1 << k) - 1;
    return -1;
}

一些示例结果：

n=31, g=15, h=25, k=10  ->  1,073,742,846  (1000000000000000000001111111110)
n=31, g=15, h=25, k=20  ->     34,602,975  (0000010000011111111111111011111)
n=31, g=15, h=25, k=30  ->  2,146,435,071  (1111111111011111111111111111111)

（我将n、g、h、k从0到20的每个值都与暴力算法的结果进行了比较，以检查正确性，没有发现差异。）

具有 k 个 1 位的最小 n 位整数 c 是两个 g、h 位设置为 1 的 n 位整数之和（动态规划）

Smallest n-bit integer c that has k 1-bits and is the sum of two n-bit integers that have g, h bits set to 1(dynamic programming)

c++

algorithm

dynamic-programming

top-down