Return to 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 <= 25, 
  0 <= x1 <= 3 && 1 <= x3 <= 5 && 1 <= x4, 2 <= x3 + x4 <= 5, 
  2.36 x1 + 2.12 x2 + 1.89 x3 + 3.77 x4 + 2.87 x5 <= 25}, {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.

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.

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.

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 <= 25, 
  0 <= x1 <= 3 && 1 <= x3 <= 5 && 1 <= x4, 2 <= x3 + x4 <= 5, 
  2.36 x1 + 2.12 x2 + 1.89 x3 + 3.77 x4 + 2.87 x5 <= 25}, {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.