How to use the algorithm of dynamic programming to find out the optimal selection scheme of this knapsack problem?

Question

Take out a certain number of items from M items and put them in a bag with a space of W. the volume of each item is V1, V2 to Vn, and the corresponding value is P1, P2 to PN. The quantity of each item is N1, N2 to NN, which items can be put into the backpack to maximize the total value.

    name = {"A", "B", "C", "D", "E"}
    V = {91, 71, 105, 103, 96};
    P = {2.36, 2.12, 1.89, 3.77, 2.87};
    "N" = {3, Infinity, 5, Infinity, Infinity};
    W = 50;
KnapsackSolve[<|"A" -> {91, 2.36, 3}, "B" -> {71, 2.12}, 
  "C" -> {105, 1.89, 5}, "D" -> {103, 3.77}, "E" -> {96, 2.87}|>, 50]

In addition, I also require that $C$ and $D$ must be selected. The sum of $C$ and $D$ must be greater than or equal to 2 and less than or equal to 5.But the MMA built-in function KnapsackSolve mentioned above cannot add additional constraints. How to use the algorithm of dynamic programming to find the optimal collocation scheme satisfying all constraints.

Maximize[{91 x1 + 71 x2 + 105 x3 + 103 x4 + 96 x5, 
  2.36 x1 + 2.12 x2 + 1.89 x3 + 3.77 x4 + 2.87 x5 <= 50, 
  0 <= x1 <= 3 && 1 <= x3 <= 5 && 1 <= x4, 2 <= x3 + x4 <= 5}, {x1, x2, x3,
   x4, x5}, NonNegativeIntegers]

It is hoped that the result of dynamic programming algorithm can be consistent with that of MMA built-in function Maximize as much as possible.

Answer 1

W = 50;
V = {91, 71, 105, 103, 96};
P = {2.36, 2.12, 1.89, 3.77, 2.87};
ub = {3, Infinity, 5, Infinity, Infinity};

KnapsackSolve[Transpose@{V, P, ub}, W]
{3, 9, 5, 0, 5}

Using LinearProgramming we get the same result:

LinearProgramming[-V, {P}, {{W, -1}}, Thread[{0, ub}], Integers]

{3, 9, 5, 0, 5}

Constraints that specify lower bounds on item counts can be handled easily by changing the arguments. For example,

lb = {0, 0, 1, 1, 0}; (* items 3 and 4 should be included in the 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]

{3, 0, 4, 1, 11}

Adding the constraint that exactly one unit of item 2 is in the solution:

ub3 = {3, 1, 5, Infinity, Infinity};
lb3 = {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[{lb3, ub3}], 
  Integers]

{2, 1, 4, 1, 11}

Answer 2

I use genetic algorithm to find the near optimal solution, but this method can' t deal with the integer point situation and the calculation speed is very slow:

clear

P0 = 0.2;

num = 100;

constraints = (2.36 x1 + 2.12 x2 + 1.89 x3 + 3.77 x4 + 2.87 x5 <= 
     25) && (0 <= x1 <= 3 && 0 <= x2 && 1 <= x3 <= 5 && 1 <= x4 && 
     0 <= x5) && (2 <= x3 + x4 <= 5);
vars = {x1, x2, x3, x4, x5};
imreg = ImplicitRegion[constraints, Evaluate@vars];
Rho = 0.6;


caltau[{a_, b_, c_, d_, e_}] := 
  If[constraints /. Thread[vars -> #] &@{a, b, c, d, e}, 
   91 a + 71 b + 105 c + 103 d + 96 e, 8000];
ants = RandomPoint[imreg, num];
taus = Map[caltau[#] &, ants];

selectbest[antss_, tau_List, lamuda_] := 
 Module[{sants = Round /@ antss, taubest = Max[tau], taumin, p, 
   lsindex, gsindex, objvalue, sobjvalue, tindex},(*sants=ants;*)
  taubest = Max[tau];
  taumin = Min[tau];

  p = Abs[taubest - tau];
  lsindex = Flatten[Position[p, n_ /; n < P0], 1];
  gsindex = Flatten[Position[p, n_ /; n >= P0], 1];
  If[Length[lsindex] >= 1, r = RandomPoint[imreg, Length[lsindex]];
   sants[[lsindex]] = sants[[lsindex]] + r*lamuda;];

  If[Length[gsindex] >= 1, r = RandomPoint[imreg, Length[gsindex]];

   sants[[gsindex]] = sants[[gsindex]] + r;

   sants = RegionNearest[imreg, #] & /@ sants;];

  objvalue = Map[caltau[#] &, antss];
  sobjvalue = Map[caltau[#] &, sants];
  tindex = Flatten[Position[Negative[sobjvalue - objvalue], True]];
  sants[[tindex]] = antss[[tindex]];
  sants
  ]

t = 1;
Do[ants = selectbest[ants, taus, 1/t]; 
 taus = (1 - Rho)*taus + Map[caltau[#] &, ants]; t++;(*Print[t]*), 50]
Map[caltau[#] &, ants]
constraints /. Thread[vars -> #] & /@ ants

Maximize[{91 x1 + 71 x2 + 105 x3 + 103 x4 + 96 x5, 
  2.36 x1 + 2.12 x2 + 1.89 x3 + 3.77 x4 + 2.87 x5 <= 25, 
  0 <= x1 <= 3 && 1 <= x3 <= 5 && 1 <= x4, 2 <= x3 + x4 <= 5}, {x1, 
  x2, x3, x4, x5}, NonNegativeReals]