b) Prove that the greedy choice will be part of at least one optimum solution using proof of contradiction.
3.
There are n different items. The i-th item is worth v_{i} dollars and weighs w_{i} pounds. You are given a knapsack of capacity W pounds and want to take as much items as possible to maximize the values you take. You can take fractions of items, and the value will be proportional to the fraction to take.
* In all problems, assume the optimal substructure is given already.
a) Design a greedy
b) Prove that the greedy choice will be part of at least one optimum solution using proof of contradiction.
c) Suppose we are given the 0-1 knapsack problem instead of the fractional one. Explain why the proof in part B will not hold in the 0-1 knapsack problem.
Step by step
Solved in 2 steps
