Answer to Question #268990 in Algorithms for heh

Question

An investment firm wants to sell N shares of a particular stock. The firm receives “m” bids of the form “ni shares for ₹ ri”. How will you characterize this as fractional knapsack problem and 0-1

Knapsack problem.

Bidders are only interested in acquiring their complete order. If the the firm wants to service the maximum number of bidders, suggest an algorithm to solve the problem.

Let S = {I1, I2, I3, I4, I5, I6, I7} be a collection of items with (weight, values) pairs:

Item Weight Value I1 2 4

I2 3 6

I3 1 5

I4 3 7

 I5 1 3

 I6 2 1

 I7 1 6

Consider items are divisible (can be broken), find a subset of items that can fit into the bag of weight capacity 7 and value of the items collected in the bag should be maximized? Show your work.

Answer 1

b)

$\sum$weight $\le7$

value $\to$ max