The smallest n-bit integer c that has k 1-bit and is the sum of two n-bit integers for which g, h bits are set to 1 (dynamic programming)

Question

I am trying to solve the following problem:

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

To begin with, an n-bit integer means that we can use all bits of n , i.e. Max. the value of such an integer is 2^n - 1 . The described integer may not be present at all. Obviously, the case k > g + h has no solutions, and for g + h = k answer is simply 2^k - 1 (the first k bits are 1 bit, k - n zeros in front).

As for some examples of what the program should do:

 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 

As I think of it, this is a dynamic programming problem, and I chose the following approach: Let dp[g][h][k][n][c] be the described integer, and c optional bit for transfer. I am trying to recover possible amounts depending on the least significant bit. So dp[g][h][k][n + 1][0] is the minimum

 (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] 

Similarly, dp[g][h][k][n + 1][1] is the minimum

 (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] 

The idea is not so difficult, but I do not really understand such things, and my algorithm does not work even in the simplest cases. I chose the approach from top to bottom. It’s hard for me to consider all angular cases. I really don't know if I chose the recursion base correctly, etc. My algorithm does not even work for the simplest case for g = h = k = 1, n = 2 (answer 01 + 01 = 10 ). The answer to g = h = k = 1, n = 1 should not be the answer, but the algorithm gives 1 (which is basically why in the first example 1 is displayed instead of 2 ). So here is my awful code (only very simple 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

You can build the smallest sum based on counting the bits g, h and k, without any dynamic programming. Assuming g & ge; h (switch them otherwise), these are the rules:

k? h? g

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

h? k? g

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

h? g? k

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

Example: all k values ​​for n = 10, g = 6 and h = 4:

 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 

Or, going straight to the value of c, without first calculating a and b:

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 

which leads to this disappointing mundane code:

 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; } 

Some examples:

 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) 

(I compared the results with the results of the brute force algorithm for each value of n, g, h and k from 0 to 20 to verify the correctness and did not find differences.)

Answer 2

I am not too sure about the approach to dynamic programming. If I understand correctly, you will need to determine how to go to dp[g + 1][h][k][n] , dp[g][h + 1][k][n] , dp[g][h][k + 1][n] and dp[g][h][k][n + 1] , with and without carry bits, are functions of the previous calculations, and I'm not sure what the correct rules are for all of these.

I think an easier way to think about the problem is with the A * search tree, where each node contains two partial number candidates that need to be added, let's call them G and H. You start with node with G = 0 and H = 0 at the level m = 0 and work as follows:

• If G + H has n or fewer bits and k 1 bits, then you have found this solution!
• Otherwise, if n - m <the number of 1 bits in G + H - k
  drop node (impossible solution).
• Otherwise, if (g + h) - (1 bit in G + 1 bit in H) k - 1 bit in G + H
  drop node (nonviable candidates).
• Otherwise, separate node to a new level. Usually you make up to four children of each node, the prefix G and H with 0 and 0, 0 and 1, 1 and 0 or 1 and 1 respectively. But:
  • You can only precede G with 1 if the number of 1 bits in G is less than g, and similarly for H and h.
  • At the m level (G and H have m bits), you can only precede G with 0 if n - m> g is the number of 1 bits in G
    and similarly for H and h.
  • If G == H and g == h, you can skip one of 0 and 1 and 1 and 0, as they will lead to the same subtree.
• Continue to the next node and repeat until you find a solution or you have no more nodes to visit.

Important is the order in which you visit the sites. You must store the nodes in the priority queue / heap, so the next node is always the first node, which could potentially lead to a better solution. This is actually easy, you just need to take for each node G + H and prefix it with the required number of 1 bits to reach k; what is the best possible solution from there.

There may be better rules for discarding invalid nodes (steps 2 and 3), but the idea of ​​the algorithm is the same.