Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 3 of 3
  1. #1
    New to the CF scene
    Join Date
    Nov 2008
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Exclamation Need greedyKnapsack help!!

    Hey i've been working on this project for a while now and i just dont get how to accomplish it. can anyone help me out?

    a) In the 0-1 Knapsack problem, given n items with weights w(1), ..., w(n)
    and values v(1),...,v(n) one chooses k items such that all their weights are
    less than (or equal to) c so that the sum of the values of those items are
    maximized. The 0-1 part means that you either take the item or you don't,
    but you cannot take the item twice.

    In this problem, we still try to maximize the values of the items which have
    total weight of less than c, but this time it is possible to take an item twice.
    But when taking the item the second time, the value will be decreased by
    half, i.e. if item m is already taken so that it takes w(m) weight and adds v(m) value, the second time we take it it still adds w(m) weight, but the value this time will be v(m) / 2.

    Solve this problem using a greedy approach (your solutions need not find the
    optimal solution), by modifying the GreedyKnapsack class in the
    code.applications package by adding the method

    - public static double greedyKnapsack012(double[] p, double[]
    w, double c, int[] x )

    Your solution should have a worst case running time of O(nlogn), where n is
    the number of different items.

    b) Generalize the previous problem, so that each item m can be taken any
    number of times, but taking it the kth time will only add v(m)/k value to the
    sum. So the second time we take m, it will add v(m)/2 value, the third time
    will add v(m)/3 value etc. Implement a greedy solution to this problem as:

    - public static double greedyKnapsack01N(double[] p, double[]
    w, double c, int[] x )

    Your solution should have a worst case running time of O(nlogn + mn),
    where n is the number of different items and m is the number of (not
    necessarily distinct) items in your solution.

    Code:
    --------- My code below ---------
    
    package applications;
    
    import dataStructures.*;
    
    public class GreedyKnapsack
    {
       static class Element implements Comparable, Playable
       {
          // data members
          int id;   // object identifier
          double d; // profit density
    
          // constructor
          private Element(int theID, double theDensity)
          {
             id = theID;
             d = theDensity;
          }
    
         // method of Comparable
         /** @return true iff this < x */
         public int compareTo(Object x)
         {
            double xD = ((Element) x).d;
            if (d < xD)
               return -1;
            if (d == xD)
               return 0;
            return 1;
          }
      
          /** @return true iff this == x */
          public boolean equals(Object x)
             {return d == ((Element) x).d;}
             
          public boolean winnerOf(Playable theElement){ // define for a max winner tree
    		if (d >= ((Element) theElement).d){
    			return true;
    		}
    		else{
    			return false;
    		}
    	}
       }
    
       /** set x[i] = 1 iff object i included in knapsack, 1 <= i < p.length
         * @param p[1:p.length-1] array of profits
         * @param w[1:w.length-1] array of weights
         * @param c knapsack capacity
         * @return value of greedy knapsack filling */
         
      // ----------------------------------------------------------------
      
         
       public static double greedyKnapsack(double [] p, double [] w, double c,
                                           int [] x)
       {
          // define an element array to be sorted by profit density
          Element [] q = new Element [p.length];
          for (int i = 1; i < p.length; i++)
             // array of profit densities
             q[i] = new Element(i, p[i] / w[i]);
       
          // sort by density
          HeapSort.heapSort(q);
       
          // load in nonincreasing order of density and compute profit sum
          double profitSum = 0;      // will be sum of profits
          for (int i = p.length - 1; i > 0; i--)
          {
             int id = q[i].id;
             if (w[id] <= c )
             {// object id fits
                x[id] = 1;
                c -= w[id];
                profitSum += p[id];
             }
             else // object id does not fit
                x[id] = 0;
          }
          return profitSum;
       }
       
       public static double greedyKnapsack012(double[] p, double[] w,
        									double c, int[] x )
       	{
       		
       		
       	}
       	
       	
       public static double greedyKnapsack01N(double[] p, double[] w,
        									double c, int[] x )
    	{
    		
    		
    	}
    	
    	
    	
       /** test greedyKnapsack */
       public static void main(String [] args)
       {
          	double [] p = {0, 16, 3, 5, 4, 7};
    		double [] w = {0, 2, 2, 6, 5, 4};
    		int [] x = new int [6];
    		int n = 5;
    
    		System.out.print("Greedy value is "); //Should print 34.0
    		System.out.println(greedyKnapsack012(p, w, c, x));
    		System.out.print("x vector is ");
    		
    		for (int i = 1; i <= n; i++)
    			System.out.print(x[i] + " "); //Should print 2 1 0 0 1
    			
    		x = new int [6];
    		System.out.print("Greedy value is "); //Should print 36.533
    		System.out.println(greedyKnapsack01N(p, w, c, x));
    		System.out.print("x vector is ");
    		
    		for (int i = 1; i <= n; i++)
    			System.out.print(x[i] + " "); //Should print 5 0 0 0 0
       }
    }
    Last edited by WA; 11-26-2008 at 06:56 AM.

  • #2
    Supreme Master coder! abduraooft's Avatar
    Join Date
    Mar 2007
    Location
    N/A
    Posts
    14,849
    Thanks
    160
    Thanked 2,223 Times in 2,210 Posts
    Blog Entries
    1
    Sorry, as per the forum rules, we are not here to do the home work, though you may ask any specific questions regarding your problem.
    (Please wrap your code by [code][/code] tags while posting here.)
    The Dream is not what you see in sleep; Dream is the thing which doesn't let you sleep. --(Dr. APJ. Abdul Kalam)

  • #3
    WA
    WA is offline
    Administrator
    Join Date
    Mar 2002
    Posts
    2,596
    Thanks
    2
    Thanked 19 Times in 18 Posts
    Firstly, Java is NOT the same as JavaScript. I've moved your thread. Secondly, this looks like a homework assignment. We can't help you do the entire work for you- it's both unrealistic and is considered cheating in this case. You need to tell people exactly where within your code you need help with or need clarification on.
    - George
    - JavaScript Kit- JavaScript tutorials and 400+ scripts!
    - JavaScript Reference- JavaScript reference you can relate to.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •