2
$\begingroup$

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 → $\Omega(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.

$\endgroup$

1 Answer 1

1
$\begingroup$

If you understand the subset sum algorithm, it's not very difficult to turn it into a "two-dimensional" version.

For an element $e$, let $m(e)$ be the "money" and $c(e)$ be the "calories" of $e$.

Let $\text{opt}(i, M, C)$ be true if there exists a subset of elements $S$ such that $\sum_{e \in S}m(e) = M$ and $\sum_{e \in S}c(e) = C$, and false otherwise. Then, simply put, $$ \text{opt}(i, w_m, w_c) = \bigvee \begin{cases} \text{opt}(i-1, w_m, w_c)\\ \text{opt}(i-1, w_m - m(i), w_c - c(i)). \end{cases} $$

This is pseudo-polynomial in the target weights.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.