Balanced Partition

The following code shows how OptFlow solves the balance partition problem (Leetcode) with dynamic programming

# Author: Anonymized for paper review
# Case Study: Balanced partition
# https://leetcode.com/problems/partition-equal-subset-sum/

import optflow as flow
import numpy as np

np.random.seed(0)

N = 10
arr = np.random.randint(1, 10, N)
sum = int(np.sum(arr))
a = flow.Constant(value=arr)
s1_size = flow.Constant(value=0, dtype=flow.integer)
x = flow.Variable(cat=flow.binary, size=N, shape=(N, ))
obj = flow.Constant(value=0)

with flow.ForLoop(N) as i:
    with flow.IfCond(x[i]):
        s1_size += a[i]
    s2_size = sum - s1_size
    obj = flow.abs(s2_size - s1_size)

prob = flow.Problem(objective=obj, sense=flow.minimize)
opt_obj = prob.solve(solver=flow.dp)
print(opt_obj)
print(arr)
print(x.optimized_value)
s_1 = [a_i for a_i, x_i in zip(arr, x.optimized_value) if x_i == 0]
s_2 = [a_i for a_i, x_i in zip(arr, x.optimized_value) if x_i == 1]
print("s1 = %s, sum(s1) = %d" % (s_1, np.sum(s_1)))
print("s2 = %s, sum(s2) = %d" % (s_2, np.sum(s_2)))

Output:

1
[6 1 4 4 8 4 6 3 5 8 7 9 9 2 7 8 8 9 2 6 9 5 4 1 4 6 1 3 4 9 2 4 4 4 8 1 2
 1 5 8 4 3 8 3 1 1 5 6 6 7]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1]
s1 = [6, 1, 4, 4, 8, 4, 6, 3, 5, 8, 7, 9, 9, 2, 7, 8, 8, 9, 2, 6, 5, 1, 1], sum(s1) = 123
s2 = [9, 4, 4, 6, 3, 4, 9, 2, 4, 4, 4, 8, 1, 2, 1, 5, 8, 4, 3, 8, 3, 1, 1, 5, 6, 6, 7], sum(s2) = 122

[Run Online Demo] (password: )