(a) Develop a greedy algorithm for the multiple-choice knapsack problem. For ful

Question

(a) Develop a greedy algorithm for the multiple-choice knapsack problem. For full credit, you should first (i) describe the decision faced at each iteration of your algorithm and what constitutes the ‘greedy’ decision and (ii) describe the subproblem you end up with after making your decision at each iteration. For the knapsack problem, the answer to (i) was you were faced with the decision of which item to try to include next into the knapsack, the greedy decision was to examine item i with the largest vi si and (ii) was a knapsack problem with one less item and, possibly, less remaining capacity. You should provide the pseudocode for the algorithm. In terms of O() notation, provide the time required/number of operations of your algorithm. Hint: In the greedy algorithm for the knapsack problem, we let S represent the set of items remaining in our problem. In the greedy algorithm for the multiple-choice knapsack problem, you could still let S represent the set of items remaining in the problem.

(b) Develop a dynamic programming algorithm for the multiple-choice knapsack problem. You do not need to provide the pseudocode for the algorithm. Provide the state defininitions, the recurrence relationships between the states of your problem, the ‘base case’ for the recurrence, and determine the time required to solve the dynamic program (i.e., how long will it require to calculate the value functions for all states in our dynamic program.) Hint: you can have the states of the dynamic program be the same for the multiple-choice knapsack problem as for the knapsack problem itself.

(c) Illustrate your method on the following multiple-choice knapsack problem. We have 4 items in the problem, each with 3 variants. The entries of the following table are (vij , sij ), i.e., the entry in the ith row and the jth column represent the value and the size of the j-th variant of item i.

1

2

3

1

(8, 3)

(5, 2)

(0, 0)

2

(6, 2)

(3, 3)

(0, 0)

3

(10, 5)

(8, 4)

(0, 0)

4

(2, 1)

(3, 2)

(0, 0)

The capacity of the knapsack is C = 6. Be as clear as possible to what your method is doing at each step (for example, tell me what you are selecting in the greedy algorithm or how you are calculating the recurrence relations in the dynamic program).

1

2

3

1

(8, 3)

(5, 2)

(0, 0)

2

(6, 2)

(3, 3)

(0, 0)

3

(10, 5)

(8, 4)

(0, 0)

4

(2, 1)

(3, 2)

(0, 0)

Explanation / Answer

The knapsack problem (KP):-

it is a classic optimization problem. Due to the large number of real-world issues or problems that can be modeled as KPs,the problem comes in many flavors.

--->knapsack problems and greedy algorithms together they solve the their linear relaxations optimally.

Knapsack Problem :-
A Knapsack problem is defined by a vector of item values,
v 0, a vector of weights, w 0 and a hard total capacity, c.
A solution is a vector x indicating the amount of each item taken.
Thus, the objective is maxx v · x subject to w · x c and each
xi {0, 1} (for the discrete problem, in which items are indivisible)
or each xi [0, 1] (for the relaxed problem, R(KP), in which items
may be divisible). (The index i ranges over items.)

GreedyKP takes items in order of efficiency until the
knapsack reaches capacity, or there are no more items with positive
efficiencies.

Algorithm GreedyKp:-
Input: v, w, c, m, f, g
Output: x
x = 0
for all items i, CALCMETRIC(i, v, w, m)
i = BESTUNTAKENITEMINDEX
while !f(i, x, v, w, c) and MOREITEMSTOCONSIDER do
xi = 1
i = BESTUNTAKENITEMINDEX
xi = g(i, x, v, w, c)
return x

Multiple Choice Knapsack Problem :-

An MCKP is defined similarly to a KP, with an additional constraint over a set of types T ,
which ensures that only one item s is taken from each type set,

T T . Thus the objective is maxx v · x subject to w · x c,
sT xs 1, T T , and each xi {0, 1}, with R(MCKP)
defined analogously.
GreedyMCKP, with efficiency as the metric m,
the hard capacity stopping rule as f, the soft taking rule as g, solves
R(MCKP) optimally.
algorithm proceeds in three steps:-

first it transforms the given instance of MCKP into a KP ; second it solves the
ensuing KP optimally using GreedyKP; third it maps the resulting

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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