Talk:Knapsack problem/Bounded: Difference between revisions
→J approach (dynamic variant)
Line 16:
A related problem is keeping track of the "best choice so far". There might be some clever way of extracting it from the values cache, but I used a best choice cache. For item <math>i</math> which has maximum possible count <math>p_i</math> and current best count <math>c_i</math>, I represent the best combination so far as <math>c_i + P_i</math> where <math>P_i = \prod 1+p_j</math> where <math>j<i</math>. (This means that when I am considering various options I can ignore an option by multiplying it by 0 and then selecting the largest remaining <math>c_i</math>.)
In other words 0 means "no items", 1 means "1 map", 2 means "1 compass", 3 means "1 map and 1 compass", 4 means "1 water", 8 means "2 waters", 9 means "2 waters and 1 map", 12 means "1 sandwich", and 16 means "1 sandwich and 1 water". And, of course, I cache <math>P_i</math> rather than recomputing it every time I need it.
| |||