Suppose you are playing a video game. In this game you can only carry a limited

Question

Suppose you are playing a video game. In this game you can only carry a limited amount of items. Every item has a value and your goal is to maximize the total value of items you are carrying. Specifically, you are choosing which of m items to carry where item number i has value u[ ] (for your recurrence/pseudo-code you can assume you are passed the item values in an array, v, of size m). Suppose you can only carry n items of the m available. Example: Let n = 3, m =5. If the item values are v = {5,30,17,32,40} which 3 should you choose to carry? Give a short description of a greedy algorithm which maximizes your total value for any given n, m, and v. Suppose, the game is updated so that every item, i, now has weight. w[i],in kilograms (you can assume you are passed the item weights in an array.w, of size m). You can only carry n kilograms of weight. Example: Let n = 15, m = 5. If the item values are v = {5,30.17,32,40} and the item weights are w = {2.4.3,6,15} which should you choose to carry? Which would your greedy algorithm choose to carry? Let V(n,m) denote your maximum total value for any given n, m. v, and w. Give a recursive definition of V: Base case Recursive case Based on your recurrence, write the pseudo-code for a dynamic programming algorithm to compute the maximum total value (you can use either bottom up dynamic programming or memoiza-tion).

Explanation / Answer

(1) (a)

                Carry the 3 items are the items with the maximum values: 30, 32, 40

(b)          Greedy algorithm is an algorithm that will find the maximum value or maximize the total value of the item that can be carried

it accepts n,m, and array v as input and outputs the maximum value

(2) (a)

weights are introduced

we have an upper ceil or maximum limit on the weight that can be carried

n = 15 kg of maximum weight can be carried

value

weight

5

2

30

4

17

3

32

6

40

15

value: 5,+ 17+,30+,32 = 84   ( weights: 2+3+4+6 = 15 kg)

hence by carrying the first 4 items with the values 5,17, 30, and 32 with the weight of 15, we get the maximum value of 84

The greedy algorithm will carry these 4 items

2 (b)

V (n, m) = total value for any given values of n, m, v, and w

start

Choose values ()

input parameters: n the maximum weight, m the number of items,

                v the array of values, w the array of weights

                for i from 1 to number of items, start loop:

                                if w[i] < n then add v[i] to the chosen item list

                                                else recursively call the Choose values () function with tis item and weight removed from both the arrays

so that the function will compare the rest of the elements

return value from the function

end function

value

weight

5

2

30

4

17

3

32

6

40

15

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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