Algorithms
Lecture ((
Knapsack & NP
2018
Knapsack Problem
Ø Knapsack Problem:
• The famous knapsack problem:
o A museum has 𝑛 different objects (items)
o Each item 𝑖 has two properties:
ü Its weight 𝑤$ (in grams)
ü Its cost 𝑣$
o A thief breaks into a museum.
o The thief has only a single knapsack.
o Caring a knapsack with maximum 𝑊 pounds
o What items should the thief take to maximize the total value?
• Formal Definition of Knapsack Problem:
o Input:
ü A set 𝑆 of 𝑛 items in which each item 𝑥$ is associated
with having
Þ 𝑉$ : positive cost.
Þ 𝑊$ : positive weight.
o Goal:
ü select set of items in 𝑆 with the constraint
Þ Maximize total benefit
Þ Weight at most 𝑊
o Objective: ∑+$,- 𝑉$
o Constraint: ∑+$,- 𝑤$ ≤ 𝑊, 𝑊>0
Lecture 11 Page 1
• Knapsack Problem:
1. 0-1 knapsack problem
2. Fractional knapsack problem
• Difference between 0-1 knapsack problem and Fractional
knapsack problem:
o 0-1 knapsack problem:
ü items cannot be divided
ü either take the item or leave it.
ü can be solved using dynamic programming.
o Fractional knapsack problem:
ü items are divisible
ü take any fraction of an item
ü like gold dust, liquids or powders.
ü can be solved using a greedy algorithm.
• Fractional knapsack problem algorithm:
o Step 1: Sort items 𝑋$ in decreasing order according to value
per weight
𝑉- /𝑊- > 𝑉4 /𝑊4 > … . > 𝑉+ /𝑊+
o Step 2: For all items 𝑋$ in the sorted list
ü Step 3: While current total weight < the limit weight (W)
Þ Step 4: consider next item in sorted list and
possibly a fraction of it.
Þ Step 5: add what was taken to load
Þ Step 6: choose as much as possible of items
Lecture 11 Page 2
• Analysis of Fractional knapsack problem algorithm
𝑂 (𝑛 lg 𝑛)
• Example 1:
o Consider the following items, each associated with cost and weight,
and weight limit (𝑊 = 50)
Solve the following using:
a) 0-1 knap sack problem
b) Fractional knapsack problem
Solution:
a) 0-1 knap sack problem: greedy solution
ü Take items 1 and 2
ü 𝑉 = 60 + 100 = 160,
𝑊 = 10 + 20 = 30
ü Have 20 pounds of
capacity left over.
Optimal solution
Lecture 11 Page 3
b) Fractional knapsack problem
ü Take items 1 and 2 and fraction of 3.
ü 𝑉 = 240, 𝑊 = 50.
ü No capacity left over.
• Example 2:
o Consider the following items, each associated with benefit and
weight, and weight limit (𝑊 = 10 𝑚𝑙 ) , Apply Fractional
knapsack algorithm
Solution:
Order: item 5, item 3, item 4, item 2, item 1
Lecture 11 Page 4
NP-Completeness
Ø Polynomial time:
• Worst case running time: 𝑂 (𝑛G ), where
o 𝑛 is the input size
o 𝑘 is a constant
• Problems solvable in p-time are considered tractable, or easy.
• NP-complete problems have no known p-time solution, considered
intractable, or hard.
• 𝑃 ≠ 𝑁𝑃
o No polynomial-time algorithm has yet been discovered for an NP-
complete problem, nor has anyone yet been able to prove that no
polynomial-time algorithm can exist for any one of them.
• three classes of problems:
1. P,
2. NP, and
3. NPC
Lecture 11 Page 5
Ø P-Problem:
• The class P consists of those problems that are solvable in polynomial
time.
• More specifically, they are problems that can be solved in time 𝑂(𝑛G )
for some constant 𝑘, where 𝑛 is the size of the input to the
problem.
Ø NP-Problem:
• The class NP consists of those problems that are verifiable in
polynomial time.
o If we are somehow given a certificate of a solution, then we could
verify that the certificate is correct in time polynomial in the
size of the input to the problem.
• Any problem in P is also in NP, since if a problem is in P then we can
solve it in polynomial time without even being supplied a certificate
(i.e. 𝑃 ⊆ 𝑁𝑃).
Ø NP-complete:
• if it is in NP and is as hard as any problem in NP.
• any NP-complete problem can be solved in polynomial time, then
every problem in NP has a polynomial time algorithm.
Ø SAT:
• A boolean formula is satisfiable if there exists some assignment of
the values 0 and 1 to its variables that causes it to evaluate to 1.
• SAT is NP-Complete
Lecture 11 Page 6
Ø Difference between P, NP, and NPC:
Problem Type Verifiable in P time Solvable in P time
P Yes Yes
NP Yes Yes or No
NPC Yes Unknown
Lecture 11 Page 7
