Lab 6 The Knapsack Problem (Continued) solution


Original Work


5/5 - (1 vote)

Problem Definition
This is a continuation of the Knapsack Problem that we worked on last week. This week, your job is to implement a greedy algorithm to (approximately) solve the Knapsack Problem. The greedy algorithm must sort the items in descending order of their value/weight ratios. You must implement either Mergesort or Quicksort for sorting. (In class, I had asked you to do both, but I feel that you should perhaps just implement one of the two. Think about the two algorithms for sorting and pick the one that you think is easier.)
0.1 Command Line Arguments
The command line format has been changed slightly. It is as follows: