Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 3 of 3
Thread: Need greedyKnapsack help!!

11262008, 06:34 AM #1
 Join Date
 Nov 2008
 Posts
 1
 Thanks
 0
 Thanked 0 Times in 0 Posts
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 01 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 01 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.length1] array of profits * @param w[1:w.length1] 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; 11262008 at 06:56 AM.
11262008, 06:57 AM
#2
 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)
11262008, 06:58 AM
#3
 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.