A Multichoice Knapsack problem variant? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T20:53:59Z http://mathoverflow.net/feeds/question/99282 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/99282/a-multichoice-knapsack-problem-variant A Multichoice Knapsack problem variant? Bonaqa 2012-06-11T10:15:28Z 2012-06-11T10:15:28Z <p>Hi All, </p> <p>my problem is a variant of menu-selection-multiple-choice-knapsack-problem. We have to select a meal of $N$ courses (one dish for every course) s.t. calorie count $k$ is minimized, whereas we remain within the specified budget $S$ and total selection should have at least a weight of $L$ kg. </p> <p>So every dish has 4 parameters:</p> <ol> <li>course $(i)$ e.g. main dish, dessert, etc. Total courses: $m$ namely: $\{N_1,N_2,N_3,...,N_m \}$ </li> <li>price $(s)$</li> <li>weight $(l)$ </li> <li>calorie count $(k)$. </li> </ol> <p>So the problem is:</p> <p>$minimize: \sum_{i=1} ^m \sum_{j \in N_i} k_{ij} x_{ij}$</p> <p>s.t.</p> <ol> <li><p>$\sum_{i=1} ^m \sum_{j \in N_i} l_{ij} x_{ij} \ge L,$</p></li> <li><p>$\sum_{i=1} ^m \sum_{j \in N_i} s_{ij} x_{ij} \le S,$</p></li> <li><p>$x_{ij} \in \{ 0,1 \}, \quad i=1,...,m, \quad j \in N_i,$</p></li> <li><p>$\sum_{j \in N_i} x_{ij} = 1 \quad \quad i=1,...,m.$</p></li> </ol> <p>this can be read as:</p> <ol> <li>Total weight should at least be $L$</li> <li>Total price should be at most $S$</li> <li>A dish cannot be partially (fractionally) selected</li> <li>at least one dish should be selected for each course.</li> </ol> <p>I tried solving the problem with following dynamic programming. But, I got stuck at implementing weight constraint. Budget constraint is easier i.e. till the remaining budget is more than the price of dish, we can consider the dish. <strong>But what to do with Weight constraint?</strong> specially because its "greater than" and not "less than". Any help/pointer here?</p> <pre><code>for i in all courses upto m do for s in all budgets upto S do for l in all Weights upto L do for j in all dishes belonging to i do s_pr = price of j l_pr = weight of j k_pr = calorie count of j if s &gt;= s_pr: PTable[i][l][s] = min(PTable[i][l][s] , PTable[i - 1][l-l_pr][s - s_pr] + k_pr) end if end for end for end for end for </code></pre> <p>All the cells of the table PTable have been initalized with $-\infty$, Except the initial 'plane', which is zero.</p> <p>Thanks in advance.</p>