Knapsack with two sums and two sets

Question

For an algorithm homework, I'm asked to give a solution for a knapsack problem. I have in input a list of products. A product is assigned a cost and a number of calories. So I have two sets, one of money and one of kcal. My goal is to choose products that give an equal sum of money and kcal.

for example if I have this input: (1, 3), (2, 4), (5, 8), (4, 5)

and the money sum equal to m=7 and kcal sum equal to k=12, I need to choose products that satisfies the two sums exactly. In my example I will choose the products (2, 4) and (5, 8). My solution only needs to return true if there exists products that match the requirement, otherwise return false. No need to return a set of products

I already wrote a solution using recursion based on the subsetsum problem, where I recall my function using the last product or not. This solution works, but it's too slow -> 2^n.

def isSubsetSum(set, n, sum, set2, sum2):
    if (sum == 0 and sum2==0):
        return True
    if (n == 0 or (sum < 0 or sum2 < 0)):
        return False
        
    if (set[n] > sum) or (set2[n] > sum2):              # if one of the two values (money, calories) is bigger than the sum 
        return isSubsetSum(set, n-1, sum, set2, sum2)   # we avoid using this product -> recall with n-1

    inclusion = isSubsetSum(set, n-1, sum-set[n], set2, sum2-set2[n]) # we recurse includig the last product
    exclusion = isSubsetSum(set, n-1, sum, set2, sum2)  # we recurse excluding the last product

return inclusion or exclusion

I tried to change my subsetsum function into a dynamic programming approach, but I have difficulties in changing my function to work with the two sets (set of money and set of calories).

I talked with the teaching assistants, and they oriented me in choosing the knapsack problem instead of the subset sum problem. I saw how the knapsack dynamic programming approach is, but I have the same problems as before with subsetsum in changing the problem to work with my input.

I think I am missing something, it would be cool if you could help me understand where I'm wrong.

Thanks

user_13014172 · Answer

Here is how a dynamic programming approach could look like:

import numpy as np

M = 7 
K = 12
products = [(1, 3), (2, 4), (5, 8), (4, 5)]

# For an empty list of products, only the problem with m=k=0 is solvable:
solvable = np.zeros(shape=(M + 1, K + 1), dtype=bool)
solvable[0, 0] = True

def one_more(product, solvable):
    result = solvable.copy()
    m_inc, k_inc = product
    for m in range(m_inc, M + 1):
        for k in range(k_inc, K + 1):
            if not solvable[m, k]:
                result[m, k] = solvable[m - m_inc, k - k_inc]
    return result

for product in products:
    solvable = one_more(product, solvable)

# The full problem of interest:
print(solvable[M, K])

NumPy is useful here, because it provides a two-dimensional array data structure, but you could achieve the same effect with nested lists.

We start with the target values M and K as constants and a given list of products. The key idea is to iterate over the list of products, starting with 0 products and adding one product at a time, each time updating a matrix (solvable) that indicates which subproblems are solvable for the given partial list of problems.

More concretely, solvable[i, j] is True if the problem with m=i and k=j is solvable with the current partial list of products.

The function one_more() updates the solvable matrix for adding one more available product. Subproblems that have not been solvable without this new product become solvable if the subproblem with m and k reduced by the values of the new product is already solvable.

Once we have updated solvable with all the products, we can look up the solution of interest in the bottom right corner of this matrix.

Knapsack with two sums and two sets

1 Answers