Scribd
Upload
37 views3 pages

Branch-and-Bound Knapsack Method

The document discusses the Branch-and-Bound method for solving the Knapsack Problem, focusing on maximizing benefits while adhering to resource constraints. It highlights the importance of the ratio of benefit to resource used for ranking items, where higher ratios indicate more favorable 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
37 views3 pages

Branch-and-Bound Knapsack Method

The document discusses the Branch-and-Bound method for solving the Knapsack Problem, focusing on maximizing benefits while adhering to resource constraints. It highlights the importance of the ratio of benefit to resource used for ranking items, where higher ratios indicate more favorable 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
i
The Branch-and-Bound Method : Knapsack Problem : Example

&
her eşya ya alının

ya alınmaz
.

Item ci/ai Ranking Özel!k


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