Add the constraints (1) item 3 and item 4 should be selected and (2)Constraints that specify lower bounds on item 3 and 4 total shouldcounts can be between 2 and 5:handled easily by changing the arguments. For example,
lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should be included in the knapsack*knapsack *)
lb + KnapsackSolve[Transpose@{V, P, ub - lb}, W - P.lb]
{3, 14, 5, 1, 0}
which is the same as LP
solution under the same constraints:
LinearProgramming[-V, {P}, {{W, -1}}, Thread[{lb, ub}], Integers]
{3, 14, 5, 1, 0}
Similarly, to add an additional constraint that requires having exactly 1 unit of item 2 in the solution we make the lower and upper bounds for that item 1:
ub2 = {3, 1, 5, Infinity, Infinity};
lb2 = {0, 1, 1, 1, 0};
lb2 + KnapsackSolve[Transpose@{V, P, ub2 - lb2}, W - P.lb2]
{0, 1, 5, 1, 12}
LinearProgramming[-V, {P}, {{W, -1}}, Thread[{lb2, ub2}], Integers]
{0, 1, 5, 1, 12}
For constraints that involve multiple items (e.g., total count of items 3 and 4 should be between 2 and 5) I am not aware of a general method to get KnapsackSolve
to work, but LinearProgramming
can handle any linear constraint easily:
For the case with the constraints (1) items 3 and 4 should both be present, and (2) total count of items 3 and 4 should be between 2 and 5, we can use:
LinearProgramming[-V,
{P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
{{W, -1}, {2, 1}, {5, -1}},
Thread[{lb, ub}],
Integers]
AddAdding the constraint that exactly one unit of item 2 is in the solution:
ub2ub3 = {3, 1, 5, Infinity, Infinity};
lb2lb3 = {0, 1, 1, 1, 0};
LinearProgramming[-V,
{P, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 0}},
{{W, -1}, {2, 1}, {5, -1}},
Thread[{lb2lb3, ub2ub3}],
Integers]