Skip to main content
3 of 7
edited body

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

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.