Dynamic Programming Knapsack Models
Translated by
ScribdTranslationsDynamic Programming Knapsack Models
Translated by
ScribdTranslationsSan Simón University
Operational Research II
Degree: Financial Engineering
Lic. Alvaro Jesus Nina Laura
LABORATORY 9
DYNAMIC PROGRAMMING - KNAPSACK METHOD
A truck has a capacity of 14 tons to transport three types of products: P1, P2, and P3. The weights
Each of these products and their respective uses are presented in the following
table
Product Weight Utility $us
P1 3 Tn 15
P2 2 Tn 12
P3 3 Tn 25
It has been determined that at least one product of type P1 and P3 must be delivered. And of P2 for the
minus 2 products.
2. Suppose you are going to fill a 20-pound backpack with the products from the following table. What with
What should be filled in the backpack if one wishes to maximize total benefit? If at least one must be taken.
item of each product
Product Weight (Lb) Utility $us
P1 4 11
P2 3 7
P3 5 12
3. Use dynamic programming to solve a knapsack type model where it holds up to 13.
kilograms. At least one item of each product must be carried
Product Peso (Kg) Utility $us
A 3 15
B 4 50
C 2 25
San Simón University
Operational Research II
Career: Financial Engineering
Lic. Alvaro Jesus Nina Laura
4. Use Dynamic Programming to solve a knapsack model where it can hold up to 15
kilograms. At least one item of each product must be brought
Product Weight (Kg) Unit cost Unit Selling Price
$us $us
A 5 15 28
B 1 50 65
C 2 25 37
5. Use dynamic programming to solve a knapsack model where it can hold up to 18
kilograms. At least one item of each product must be taken
Product Weight (Kg) Unit cost $us Selling Price
Unit price $us
A 6 22 56
B 9 45 65
C 4 55 70