"""
Discrete knapsack problem in cpmpy.

Port of the MiniZinc model from
https://stackoverflow.com/questions/69542783/minizinc-discrete-knapsack-problem-%d0%90n-incomprehensible-solution

Showing all the optimal solutions:
max_profit: 5 sum_weights: 5 selected: E
max_profit: 5 sum_weights: 5 selected: B C
max_profit: 5 sum_weights: 5 selected: A D


Model created by Hakan Kjellerstrand, hakank@hakank.com
See also my CPMpy page: http://www.hakank.org/cpmpy/

"""
import itertools
from cpmpy import *
import numpy as np
from cpmpy_hakank import *
import copy

def discrete_knapsack(profits,weights,names,capacity):

    
    print("profits:",profits)
    print("weights:",weights)
    print("capacity:",capacity)

    n = len(profits)

    # decision variables
    x = boolvar(shape=n,name="x")
    max_profit = intvar(0,sum(profits),name="max_profit")
    sum_weights = intvar(0,sum(weights),name="sum_weights")

    model = Model([max_profit == (x*profits).sum(),
                   sum_weights == (x*weights).sum(),
                   sum_weights <= capacity,
                   ])

    model2 = copy.copy(model)
    model2.maximize(max_profit)

    model2.solve()
    opt = max_profit.value()
    print("\nFind all optimal solutions of max_profit",opt)

    def print_sol():
        print("max_profit:",max_profit.value(),"sum_weights:", sum_weights.value(),"selected:"," ".join(names[x.value() == 1]))

    model += [max_profit == opt]
    num_solutions = model.solveAll(solution_limit=0,display=print_sol)
    print()
    print("num_solutions:", num_solutions)  

profits = [1,2,3,4,5]
weights = [1,2,3,4,5]
names   = np.array(['A','B','C','D','E'])
capacity = 5
discrete_knapsack(profits,weights,names,capacity)