## 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: