One approach to solving the knapsack problem is to select items in decreasing or
ID: 3619914 • Letter: O
Question
One approach to solving the knapsack problem is to select items in decreasing order of value-to-weight ratio, starting from the highest ratio, until the weight limit prevents the selection of any more items. This is called the Greedy method.a. Construct a four-item knapsack problem for which the greedy method is optimal. That is, contrive a specic instance of the knapsack problem (with unambiguous numerical values for the value and weight of each item, along with a numerical value for the weight limit of the knapsack), such that the greedy method produces an optimal solution. Verify by hand that the solution computed by the greedy
method is optimal (show your work!).
b. Comment on how you would answer the part a. above if you had been asked to have a list with at least 100 items. (Comment particularly on how you would verify that the solution is optimal.)
c. Construct a knapsack problem for which the greedy method is not optimal, and present proof to that effect. Make sure you have at least 4 items available for inclusion in the knapsack.
Explanation / Answer
Note: I have edited my response...
I made a mistake understanding this in my earlier response (which I have edited now). In fact the last part c of this problem guided me to this way that I am making a mistake. It is not fractional knapsack, it is 0/1 knapsack. A fractional knapsack is always optimal. And I also applied dynamic programming solution to the above problem and not greedy algorithm.
a. Construct a four-item knapsack problem for which the greedy method is optimal. That is, contrive a specific instance of the knapsack problem (with unambiguous numerical values for the value and weight of each item, along with a numerical value for the weight limit of the knapsack), such that the greedy method produces an optimal solution. Verify by hand that the solution computed by the greedy method is optimal (show your work!).
Knapsack can hold Weight 60
Item 1: Value = 100, Weight = 20
Item 2: Value = 160, Weight = 40
Item 3: Value = 60, Weight = 55
Item 4: Value = 100, Weight = 45
Now, above situation gives optimal solution, because using greedy algorithm, we will choose item 1 and item 2 and our total value will come out to be 100+160=260 and our knapsack will be filled too. No other combination of items will give value greater than or equal to 260, therefore, it is the optimal solution.
b. Comment on how you would answer the part a. above if you had been asked to have a list with at least 100 items. (Comment particularly on how you would verify that the solution is optimal.)
For 100 items, I will more likely to use a computer program, because it will be more error prone and time consuming to solve the problem for 100 items.
Regarding verifying that whether the solution I obtained for 100 items is optimal or not. I will run dynamic programming algorithm for 0/1 Knapsack and then compare the results obtained with greedy algorithm. Note that dynamic programming algorithm for 0/1 knapsack problem always gives optimal solution.
For 100 items, it will be very tedious to verify by hand that solution is optimal or not. It can be verified by hand for small number of items say up to 5 or 10.
c. Construct a knapsack problem for which the greedy method is not optimal, and present proof to that effect. Make sure you have at least 4 items available for inclusion in the knapsack.
Knapsack can hold Weight 60
Item 1: Value = 30, Weight = 5
Item 2: Value = 100, Weight = 20
Item 3: Value = 160, Weight = 40
Item 4: Value = 90, Weight = 30
Sort by value to weight ratio
Item 1: 30/5 = 6
Item 2: 100/20 = 5
Item 3: 160/40 = 4
Item 4 = 90/30 = 3
First take 1st item, its weight is 5, it can fit in the bag, therefore,
Remaining weight knapsack can hold = 60
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.