0

I have a python code which solves the 3-Partition problem using Dynamic Programming method. But I don't really understand how he utilizes the DP method. Could anyone tell me what is the recursion formula in this code and why it works? (Especially the middle loop part)

import sys
def partition3(A):
   n = len(A)
   if sum(A)%3 != 0:
       return 0
   W = sum(A)//3
   value = [[[0 for x in range(W+1)] for y in range(W+1)] for z in range(len(A)+1)]
   #print("dimension,n:",len(value[0][0]), len(A))
   value[0][0][0] = 1
   for idx in range(len(A)+1):
       value[idx][0][0] = 1

   for i in range(1, n+1):
       for j in range(W+1):
           for k in range(W+1):
            
             value[i][j][k] = value[i-1][j][k]
             
             if (j >= A[i-1] and value[i-1][j-A[i-1]][k]):

                value[i][j][k] = 1
             if (k >= A[i-1] and value[i-1][j][k-A[i-1]]):
                value[i][j][k] = 1
   for idx in range(n+1):
        print(value[idx][0][:])
   if(value[len(A)][W][W] == 1):
        return 1
   else:
        return 0


if __name__ == '__main__':
   input = sys.stdin.read()
   n, *A = list(map(int, input.split()))
   print(partition3(A))
khelwood
  • 55,782
  • 14
  • 81
  • 108
DavidMonet
  • 1
  • The recursive formula corresponds to this part: `value[i][j][k] = value[i-1][j][k] if (j >= A[i-1] and value[i-1][j-A[i-1]][k]): value[i][j][k] = 1 if (k >= A[i-1] and value[i-1][j][k-A[i-1]]): value[i][j][k] = 1` – Stef Feb 02 '22 at 09:49
  • Which is somewhat awkward in my opinion, and could be rewritten with logic operators: `value[i][j][k] = value[i-1][j][k] or (j >= A[i-1] and value[i-1][j-A[i-1]][k]) or (k >= A[i-1] and value[i-1][j][k-A[i-1]])` – Stef Feb 02 '22 at 09:51
  • There are a few weird things in the code you pasted. For instance, it uses `1` and `0` instead of `True` and `False`. The final four lines are redundant: `if(value[len(A)][W][W] == 1): return 1 else: return 0` is equivalent to `return value[len(A)][W][W]` – Stef Feb 02 '22 at 09:53
  • Hi Stef! Thank you for your explanation and improvement. I just don’t understand what is the meaning of this recursion formula. What is the math background behind this, could you explain this to me? Thanks again! – DavidMonet Feb 02 '22 at 17:20
  • I'm afraid I'll say something false. The code you pasted doesn't explain the meaning of variables i, j and k in `value[i][j][k]`. From the dimensions of `value`, I assume `j` represents the sum of the first part in a 3-partition, `k` represents the sum of the second part (the sum of the third part must be `3*W - j - k`); and `i` represents... a number of used elements of `A`? – Stef Feb 03 '22 at 13:29
  • Oh. `i` is in `range(len(A)+1)`, but we always refer to `A[i-1]`, never to `A[i]`. So from this we can guess that `i` is never 0 (otherwise `A[i-1]` is `A[-1]` which is technically allowed, but would be super weird). So I'm guessing `i` simply represents the index of an element of `A`, and whoever wrote this code decided to use 1-indexes instead of 0-indexes, though that's a bit awkward in python. – Stef Feb 03 '22 at 13:32

0 Answers0