Geekman's Blog

Geekman's Blog

Re-choose Knapsack Problem

February 21, 2015. Posted by Rohit Mulange

A variant of the knapsack problem is where each item can be chosen any number of times. I was at first worried in class: “Shit, my dynamic programming algorithm of knapsack won’t work here”. I spent the next hour making a recursive algorithm that solved this problem.

A few hours later, when I was thinking about the problem, I realized I had been stupid and dumb! Not only was this easily possible, but it was possible by one simple change in the Knapsack Algorithm:


Knapsack Problem Algorithm:


The Implementation in Python:

The same algoritm modified to allow each element to be chosen multiple times:


Re-Choose Knapsack Problem Algorithm:


The Implementation in Python: