 Vyom World.com Let's Touch the Sky Together!        Home VyomWorld.com Home Free Magazines! VyomLinks.com Home JobsAssist.com Home Vyom Network Contact Us Jobs & Careers Resume Submitter Placement Papers IT Companies Directory Computer Jobs Interview Questions Online Exams Vyom Career eMag. Fun Screensavers New! Send FREE SMS! SMS Jokes Source Codes Library Source Codes Home ASP Source Codes C Source Codes C++ Source Codes COBOL Source Codes Java Source Codes Pascal Source Codes Submit Source Codes GATE GATE an Overview GATE Preparation Study Materal GRE GRE an Overview GRE Questions GRE Preparation GRE Universities TOEFL Preparation TOEFL Resources GMAT Preparation GMAT Resources MBA Preparation MBA Resources Networking Concepts Networking Concepts Testing Preparation Testing Resources Webmasters Free Traffic Builder Webmaster Articles Web Hosting Tutorials Hardware Tutorial 1500 Free eBooks New! FREE Publications Vyom Career eMag. Get 9,000+ Interview Questions & Answers in an eBook. 9,000+ Interview Questions All Questions Answered 5 FREE Bonuses Free Upgrades Get it now!  Get 9,000+ Interview Questions with Answers in an eBook

Analysis and Design of Algorithms

5.2 General Knapsack problem:

Greedy method is best suited to solve more complex problems such as a knapsack problem. In a knapsack problem there is a knapsack or a container of capacity M n items where, each item i is of weight wi and is associated with a profit pi. The problem of knapsack is to fill the available items into the knapsack so that the knapsack gets filled up and yields a maximum profit. If a fraction xi of object i is placed into the knapsack, then a profit pixi is earned. The constrain is that all chosen objects should sum up to M

Illustration

Consider a knapsack problem of finding the optimal solution where, M=15, (p1,p2,p3�p7) = (10, 5, 15, 7, 6, 18, 3) and (w1, w2, �., w7) = (2, 3, 5, 7, 1, 4, 1).

In order to find the solution, one can follow three different srategies.

Strategy 1 : non-increasing profit values

Let (a,b,c,d,e,f,g) represent the items with profit (10,5,15,7,6,18,3) then the sequence of objects with non-increasing profit is (f,c,a,d,e,b,g).

 Item chosen for inclusion Quantity of item included Remaining space in M PiXi f 1 full unit 15-4=11 18*1=18 C 1 full unit 11-5=6 15*1=15 A 1 full unit 6-2=4 10*1=10 d 4/7 unit 4-4=0 4/7*7=04

Profit= 47 units

The solution set is (1,0,1,4/7,0,1,0).

Strategy 2: non-decreasing weights

The sequence of objects with non-decreasing weights is (e,g,a,b,f,c,d).

 Item chosen for inclusion Quantity of item included Remaining space in M PiXI E 1 full unit 15-1=14 6*1=6 G 1 full unit 14-1=13 3*1=3 A 1 full unit 13-2=11 10*1=10 b 1 full unit 11-3=8 5*1=05 f 1 full unit 8-4=4 18*1=18 c 4/5 unit 4-4=0 4/5*15=12

Profit= 54 units

The solution set is (1,1,4/5,0,1,1,1).

Strategy 2: maximum profit per unit of capacity used

(This means that the objects are considered in decreasing order of the ratio Pi/wI)

a: P1/w1 =10/2 = 5 b: P2/w2 =5/3=1.66 c: P3/w3 =15/5 = 3

d: P4/w4 =7/7=1 e: P5/w5 =6/1=6 f: P6/w6 =18/4 = 4.5

g: P7/w7 =3/1=3

Hence, the sequence is (e,a,f,c,g,b,d)

 Item chosen for inclusion Quantity of item included Remaining space in M PiXI E 1 full unit 15-1=14 6*1=6 A 1 full unit 14-2=12 10*1=10 F 1 full unit 12-4=8 18*1=18 C 1 full unit 8-5=3 15*1=15 g 1 full unit 3-1=2 3*1=3 b 2/3 unit 2-2=0 2/3*5=3.33

Profit= 55.33 units

The solution set is (1,2/3,1,0,1,1,1).

In the above problem it can be observed that, if the sum of all the weights is £ M then all xi = 1, is an optimal solution. If we assume that the sum of all weights exceeds M, all xi�s cannot be one. Sometimes it becomes necessary to take a fraction of some items to completely fill the knapsack. This type of knapsack problems is a general knapsack problem. Discussion Center   Recently Updated: New Placement Papers added.
Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory