.
 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!


    Post your Resume to 5800+ Companies

    Reliable Web Hosting

  •  
     
     
    Get 9,000+ Interview Questions with Answers in an eBook


     Home

    Analysis and Design of Algorithms


    Advertisements
    Advertisements

    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,p3p7) = (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 xis 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.

    Study Notes Home | Next Section>>




     

    Discussion Center

    Discuss

    Query

    Feedback/ Suggestion

    Yahoo Groups

    Sirfdosti Groups

    Contact Us


    .

    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

    Copyright ©2003-2017 Vyom Technosoft Pvt. Ltd., All Rights Reserved. Read our Privacy Policy