Re-choose Knapsack Problem
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: