knapsack and graph optimization problems suppose for examplea burglar who has knapsack that can hold at most pounds of loot breaks into house and finds the items in figure clearlyhe will not be able to fit it all in his knapsackso he needs to decide what to take and what to leave behind value weight value/weight clock painting radio vase book computer figure table of items greedy algorithms the simplest way to find an approximate solution to this problem is to use greedy algorithm the thief would choose the best item firstthen the next bestand continue until he reached his limit of coursebefore doing thisthe thief would have to decide what "bestshould mean is the best item the most valuablethe least heavyor maybe the item with the highest value-to-weight ratioif he chose highest valuehe would leave with just the computerwhich he could fence for $ if he chose lowest weighthe would takein orderthe bookthe radiothe vaseand the painting--which would be worth total of $ finallyif he decided that best meant highest value-to-weight ratiohe would start by taking the vase and the clock that would leave three items with value-to-weight ratio of but of those only the book would still fit in the knapsack after taking the bookhe would take the remaining item that still fitthe radio the total value of his loot would be $ though greedy-by-density (value-to-weight ratiohappens to yield the best result for this data setthere is no guarantee that greedy-by-density algorithm always finds better solution than greedy by weight or value more generallythere is no guarantee that any solution to this kind of knapsack problem that is found by greedy algorithm will be optimal we will discuss this issue in more detail bit later the code in figure and figure implements all three of these greedy algorithms in figure we first define class item each item has namevalueand weight attribute for those of you too young to remembera "knapsackis simple bag that people used to carry on their back--long before "backpacksbecame fashionable if you happen to have been in scouting you might remember the words of the "happy wanderer," love to go -wanderingalong the mountain trackand as goi love to singmy knapsack on my back there is probably some deep moral lesson to be extracted from this factand it is probably not "greed is good