Flash Website Builder- Trendy Site Builder is a Flash Site Building tool that helps users build stunning websites. Check Out Custom Custom Logo Design by LogoBee. Website Design and Free Logo Templates available.
 CodingForums.com Need greedyKnapsack help!!

Before you post, read our: Rules & Posting Guidelines

Enjoy an ad free experience by logging in. Not a member yet? Register.
 11-26-2008, 07:34 AM PM User | #1 bigACE New to the CF scene   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 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 07:56 AM..
11-26-2008, 07:57 AM   PM User | #2
abduraooft
Supreme Master coder!

Join Date: Mar 2007
Location: N/A
Posts: 14,775
Thanks: 159
Thanked 2,213 Times in 2,200 Posts
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.
__________________
Quote:
 The Dream is not what you see in sleep; Dream is the thing which doesn't let you sleep. --(Dr. APJ. Abdul Kalam)

 11-26-2008, 07:58 AM PM User | #3 WA 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.

 Bookmarks

 Thread Tools Rate This Thread Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home :: Client side development     JavaScript programming         DOM and JSON scripting         Ajax and Design         JavaScript frameworks         Post a JavaScript     HTML & CSS     XML     Flash & ActionScript         Adobe Flex     Graphics and Multimedia discussions     General web building         Site reviews         Building for mobile devices :: Server side development     Apache configuration     Perl/ CGI     PHP         Post a PHP snippet     MySQL         Other Databases     Ruby & Ruby On Rails     ASP     ASP.NET     Java and JSP     Other server side languages/ issues         ColdFusion         Python :: Computing & Sciences     Computer Programming     Computer/PC discussions     Geek News and Humour Web Projects and Services Marketplace     Web Projects         Small projects (quick fixes and changes)         Medium projects (new script, new features, etc)         Large Projects (new web application, complex features etc)         Unknown sized projects (request quote)         Vacant job positions         Looking for work/ for hire         Project collaboration/ partnership         Paid work offers and requests (Now CLOSED)     Career, job, and business ideas or advice     Domains, Sites, and Designs for sale         Domains for sale         Websites for sale         Design templates and graphics for sale :: Other forums     Member Offers     Forum feedback and announcements

All times are GMT +1. The time now is 04:55 AM.