Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

1. ## 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
}
}```

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