Talk:Knapsack problem/Bounded: Difference between revisions

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>ij</math> which has maximum possible count <math>p_ip_j</math> and current best count <math>c_ic_j</math>, I represent the best combination so far as <math>c_i\sum c_j + P_iP_j</math> where <math>P_iP_j = \prod 1+p_jp_k</math> where <math>jk<ij</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_ic_j</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, since I am taking tiny steps at each step of coursecomputation, I cache <math>P_iP_j</math> rather than recomputing it every time I need it. (You might think of this as a generalization of base n arithmetic where each digit position can be in an independent base (except that these "digits" are probably best thought of as being arranged from left-to-right instead of the usual right-to-left).) --[[User:Rdm|Rdm]] 21:20-ish, 27 June 2011 (UTC)