The greedy method(knapsack problem)

Question

consider this instance of the knapsack problem: the weights are:15,9,27,12,36,12,9,12,the prices are :15,24,14,20,18,20,18,6,and the capacity c=50,applay the greedy method algorithm to find the solution (that is , how much of every item we are going to get).show the process of deriving the solution step by step.

Answer 1

Integer Knapsack Problems

--------------------------------------...

In various forms this is a frequently arising optimisation problem. Input: A set of items U = {u1, u2 ,..., uN}

each item having a given size s( ui ) and value v( ui ).

A capacity K.

Output: A subset B of U such that the sum over u in B of s(u) does not exceed K and the sum over u in B of v(u) is maximised.

No fast algorithm guaranteed to solve this problem has yet been discovered.

It is considered extremely improbable that such an algorithm exists.

Using a greedy approach, however, we can find a solution whose value is at worst 1/2 of the optimal value.

    * The items, U, are the candidates.

    * A subset, B, is a solution if the total size of B fits within the given capacity, but adding any other item will exceed the capacity.

    * The objective function which is to be maximised is the total value.

The selection function chooses that item, ui for which

                    v( ui )

                   --------

                    s( ui )

is maximal

(http://www.csc.liv.ac.uk/~ped/teachadmin...

Therefore the selection function for this problem is to choose the product item with the highest weight/price first and then if the capacity is not reached then move to the next highest weight/price and so on.... such that the total weight is maximized (to 50.)

wt--pr--wt/pr---selOr---qty2choose

======================================...

15--15--1.000--3rd

09--24--0.375--6th

27--14--1.929--2nd

12--20--0.600--4th

36--18--2.000--1st---1-----0        

12--20--0.600--4th

09--18--0.500--5th

12--06--2.000--1st---1-----4

======================================...

-------------------------48/50--48/50

The most probable optimal solution will be the one with the least total qty. since price will give the same value

       1(36@18)+1(12@6)=24

        and

        4(12@6)=24

Therefore 2 qty (1(36@18) and 1(12@6)) is the most probable optimal solution.

(Note:The best change is the one with the least number of coins)

Answer 2

∑pq→MAX

(because of "greedy" approach task is to load back-pack with maximal value=price*quantity)

∑wq≤50

(total weight is limited)

Product Weight .. Price . Q-ty  TotalPrice TotalWeight

.....1 ....... 15 ....... 15 ....... 0 ....... 0 ....... 0

.....2 ........ 9 ........ 24 ....... 5 .. 1080 ..... 45

.....3 ....... 27 ....... 14 ....... 0 ....... 0 ....... 0

.....4 ....... 12 ....... 20 ....... 0 ....... 0 ....... 0

.....5 ....... 36 ....... 18 ....... 0 ....... 0 ....... 0

.....6 ....... 12 ....... 20 ....... 0 ....... 0 ....... 0

.....7 ........ 9 ........ 18 ....... 0 ....... 0 ....... 0

.....8 ....... 12 ......... 6 ....... 0 ....... 0 ....... 0

_________ _________ _________ _________

Total ........ X ........ X ........ 5 ... 1080 ..... 45

This is just final result of relevant programming solution, but analytical is simple too, you just need to solve it using marginal utility concept (utility is given in "price" column) taking into account weight limitation constraint.

In this simple task if you will sort products by weight you will see that lowest weight gives you also maximal price - so you have no other opportunity than load full pack with this product. So this one is solved in one-step. Another tasks could include limits of available products.

Step-by-step solution is lengthy, but I think that people from "Mathematics" category will do it for you if you will ask them.

P.S. The guy below me is actually wrong because he misinterptered "greedy" method - he has maximized more weight rather than value, if you will use his data you will get total loaded value in your back-pack of:

Product No: ...5...... .8......∑

Quantity...... ..1........1 .....2

Weight...... ...36......12 .. 48

Price......... ...18.......6 .....X

Product..... ..648......72....720

So total value is only 720

But my solution gives you value in back-pack of 1080  !!!.