knapsack problem

Coordinator
Jul 15, 2014 at 10:55 PM
public class KnapSackTest{

public class Item
{
public float weight,value;
public int index;

Item(float w, float v,int i)
{
  weight=w;
  value=v;
  index=i;
}
}

public static main(string args[])
{
Item[]    items;


items[0]=new Item(1,90.72,13);
items[1]=new Item(2,33.80,40);
items[2]=new Item(3,43.15,10);
items[3]=new Item(4,37.97,1);
items[4]=new Item(5,46.81,36);
items[5]=new Item(6,48.77,79);
items[5]=new Item(7,81.80,4);
items[5]=new Item(8,19.36,$79);
items[5]=new Item(9,6.76,$64);
}

public static int KnapSack(int capacity, Item[] items, int numItems, ArrayList<Integer> taken) {
if (numItems == 0 || capacity == 0)
    return 0;
if (items[numItems-1].weight > capacity)
    return KnapSack(capacity, items, numItems-1, taken);
else {
    final int preTookSize = taken.size();
    final int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1, taken);

    final int preLeftSize = taken.size();
    final int left = KnapSack(capacity, items, numItems-1, taken);

    if (took > left) {
        if (taken.size() > preLeftSize)
            taken.removeRange(preLeftSize, taken.size());
        taken.add(Integer.valueOf(numItems - 1));
        return took;

    }
    else {
        if (preLeftSize > preTookSize)
            taken.removeRange(preTookSize, preLeftSize);
        return left;
    }
}     
}
}
Coordinator
Jul 21, 2014 at 5:58 AM
import java.util.ArrayList;
import java.io.*;
import java.io.PrintWriter;

class Item{
public double weight;
public int value;
Item(double w,int v)
{
  weight=w;
  value=v;
}
}

public class KnapSackTest{

public static void main(String args[])
{

ArrayList<Integer> taken=new ArrayList<Integer> () ;
float value;
Item[] Items = new Item[9];
Items[0]=new Item(90.72,13);
Items[1]=new Item(33.80,40);
Items[2]=new Item(43.15,10);
Items[3]=new Item(37.97,16);
Items[4]=new Item(46.81,36);
Items[5]=new Item(48.77,79);
Items[6]=new Item(81.80,45);
Items[7]=new Item(19.36,79);
Items[8]=new Item(6.76,64);

PrintWriter writer = new PrintWriter("log.txt", "UTF-8");
writer.println("The first line");
writer.println("The second line");
writer.close();
value=KnapSack(56.00,Items,9,taken);

for (Integer i: taken)
{
   System.out.println("Elelemnt"+(i+1));
}
}


public static int KnapSack(double capacity, Item[] items, int numItems, ArrayList<Integer> taken) {
System.out.println("Items:"+numItems+" Taken size:"+taken.size());
if (numItems == 0 || capacity == 0)
    return 0;
if (items[numItems-1].weight > capacity) {
    System.out.println("return KnapSack(capacity, items, numItems-1, taken);");
    return KnapSack(capacity, items, numItems-1, taken);}
else {
    final int preTookSize = taken.size();
    final int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1, taken);
    double took_wt=0;
    for(Integer  i : taken)
    {
        took_wt+=items[i].weight;
    }
    final int preLeftSize = taken.size();
    final int left = KnapSack(capacity, items, numItems-1, taken);
    double left_wt=0;
    for(Integer  i : taken)
    {
        took_wt+=items[i].weight;
    }
    if ((took > left) || (took ==left && (took_wt<left_wt) )){
        if (taken.size() > preLeftSize)
            taken.subList(preLeftSize, taken.size()).clear();
        taken.add(Integer.valueOf(numItems - 1));
        System.out.print("#Items"+(numItems)+": ");
        for(Integer  i : taken)
        {
                       System.out.print("Element"+(i+1)+" ");
        }
        System.out.println("return took");
        return took;
    }
    else 
         {
            if (preLeftSize > preTookSize)            
                taken.subList(preTookSize, preLeftSize).clear(); 
            System.out.print("#Items"+(numItems)+": ");
            for(Integer  i : taken)
            {
                       System.out.print("Element"+(i+1)+" ");
             }
             System.out.println("return left");                     
            return left;
        }
   }
}     
}