Knapsack problems (see also Cormen at al.) The 0-1 knapsack problem is the follo

Question

Knapsack problems (see also Cormen at al.) The 0-1 knapsack problem is the following: a thief robbing a store finds n items. The ith item is worth v_i dollars and weighs w_i kilos with i and w_i positive integers. The thief wants to take as valuable a load as possible, but he can carry at most W kilos in his knapsack with W > 0. Which items should he take to maximise his loot? This is called the 0-1 Knapsack problem because for each item, the thief must either take it or leave it behind. He cannot take a fractional amount of an item or take an item more than once. In the fractional knapsack problem, the setup is the same, but the thief can take fractions of items, rather than having to make a binary (0-1) choice for each item. After some deep thinking the lecturer of COMP333 proposes the following modelling for the fractional knapsack problem: let S = { 1, 2, n} Opt (S, W) = p + v)j + Opt(S {j}, W - p_j middot w_j) and Opt(Y) = 0. Notice that the 0-1 knapsack problem is a particular case where p must be either 0 or 1. Prove that the fractional knapsack problem recursive solution defined by Equation I has optimal sub-structure.

Explanation / Answer

hi..

Proof

Assume there's an optimal solution A={a1,a2,...,an}A={a1,a2,...,an} to the fractional knapsack problem (FF) that does not include the item ii, with the greatest value per weight (vw)(vw) ratio of all initial items.

Suppose a1a1 is the item in the solution AA with the greatest value per weight ratio. Note that we have
vi/wiva1/wa1
vi/wiva1/wa1
Now, suppose we remove a1a1 from AA and we obtain a solution AA to a subproblem FF:
A=Aa1
A=Aa1
If we combine the solution AA (to the subproblem FF) with the greedy choice ii (or a fraction of it), we will obtain a greater (or equal) valuable solution BB, since
vi/wiva1/wa1
vi/wiva1/wa1
If BB is better than AA, then this is a contradiction, and thus ii must be included; if B=AB=A, then we have shown that the greedy choice is included anyway, since that would mean that vi/wi=va1/wa1

thanks

Related Questions

Navigate

• Browse (All)
• Browse K
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.