/*Knapsack.java
 *J Scott Cameron
 *
 *This class hilds the information for a Knapsack for use
 * with the GeneticAlgortihm class
 **/

import GeneticAlgorithm;
import KnapsackItem;
import java.util.*;
import java.io.*;


public class Knapsack{
    
    private Vector items; /* vector of possible items */
    private int capacity; /* capacity of the Knapsack */
    
    /* default construxtor */
    public Knapsack()
    {
        capacity = 0;
        items = new Vector();
    }
    
    /* parameterized constructor */
    public Knapsack(int capacity)
    {
        this.capacity = capacity;
        items = new Vector();
    }
    
    /* adds a possible item to the knapsack */
    public void addItem(int weight,int value)
    {
        items.add(new KnapsackItem(weight,value));
        
    }
    
    /* removes an item from consideration */
    public void removeItem(KnapsackItem ki)
    {
        items.remove(ki);
    }
    
    /* removes an item from consideration */
    public void removeItem(int index)
    {
        items.remove(index);
        
    }
    
    /* returns the capacity of the Knapsack */
    public double getCapacity()
    {
        return capacity;
    }
    
    /* sets the capacity*/
    public void setCapacity(int capacity)
    {
        this.capacity = capacity;
    }
    
    /* returns the number of possible items*/
    public int possibleItems()
    {
        return items.size();
    }
    
    /* returns a vector of possible items */
    public Vector getItems()
    {
        return items;
    }
    
    /* returns the fitness of a given bit array
     * this is the fitness function to be used
     * by the Genetic Algorithm */
    public int testFitness(boolean b[])
    {
        int i = 0;
        int value = 0;
        int weight = 0;
        KnapsackItem test;
        Enumeration e= items.elements();
        
        /* for every possible item
         * check to see if it is in the sack
         * and add its value and weight if it is */
        while(e.hasMoreElements())
        {
            test = (KnapsackItem)e.nextElement();
            if(b[i])
            {
                value += test.getValue();
                weight += test.getWeight();
            }
            i++;
        }
        
        /* if the sack is under weight return the value as the fitness */
        if(weight <= capacity)
        {
            return value;
        }
        /* else return the amount it is overweight as a negative fitness */
        else
        {
            return -(weight-capacity);
        }
    }
    
    /* finds the optimal knapsack by iterating through all possible
     * knapsacks */
    public boolean[] findOptimized()
    {
        int i,j;
        boolean bestB[] = new boolean[items.size()];
        int best=0;
        int test;
        boolean b[] = new boolean[items.size()];
        for(i = 0;i<items.size();i++)
        {
            b[i] = false;
        }
        
        for(i = 0;i<Math.pow(2,items.size());i++)
        {
            test = testFitness(b);
            if(test > best){
                best = test;
                for(j = 0;j<items.size();j++)
                {
                    bestB[j]=b[j];
                }
            }
            
            
            for(j=b.length-1;(j>=0);j--){
                if(!b[j]) break;}
            if(j>=0)
            {
                b[j]=true;
                j++;
                for(;j<b.length;j++)
                {
                    b[j]=false;
                }
            }
            
        }
        return bestB;
    }
}