Scribd
Upload
4 views3 pages

Branch-and-Bound Knapsack Method

The document discusses the Branch-and-Bound method for solving the Knapsack Problem, focusing on the maximization of benefits from selected items based on available resources. It highlights the simplification of the method due to binary variable constraints (0 or 1) and introduces the concept of benefit per unit of resource to rank items. An example is provided to illustrate the ranking of items based on their benefit-to-resource ratios.

Uploaded by

aydemiremhasan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views3 pages

Branch-and-Bound Knapsack Method

The document discusses the Branch-and-Bound method for solving the Knapsack Problem, focusing on the maximization of benefits from selected items based on available resources. It highlights the simplification of the method due to binary variable constraints (0 or 1) and introduces the concept of benefit per unit of resource to rank items. An example is provided to illustrate the ranking of items based on their benefit-to-resource ratios.

Uploaded by

aydemiremhasan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

The Branch-and-Bound Method : Knapsack Problem

Let be the benefit obtained if item is chosen, is the amount of available


resource and is the amount of available resource used by item .

We can then write


max = 1 1 + +
1 1 + … +
1 , … , 0,1

When knapsack problems are solved by the branch-and-bound method, two


aspects of the method greatly simplify. Because each variable must equal 0
öge kaynak
or 1.
! !ç!n 1 b!

ner ed!ler
fayda
-
elde

Additionally, observe that &


/ might be interpreted as the benefit by a unit
of resource . We can then say that the best and worst items to have are the
ones with the largest and smallest &/ , respectively.

15
The Branch-and-Bound Method : Knapsack Problem : Example

Item ci/ai Ranking


1 16/5=3.2 1 Gest
2 22/7=3.14 2
3 12/4=3 3
4 8/3=2.66 4
Est
16
17

You might also like