[JAVA] Problema dello zaino/bisaccia

[claretta]

Ciao a tutti vorei sapere se qualcuno ha fatto in java un programma sul problema dello zaino.O se può darmi qualche aiuto per iniziare.Grazie.

[stex1984]

per problema dello zaino intendi il problema della bisaccia?

[claretta]

si.In pratica ho uno zaino con capacità C e n oggetti con una dimensione e un profitto devo fare in modo di mettere nello zaino gli oggetti con il maggior profitto e che la loro dimensione non superi la capacità dello zaino.Sai darmi qualche aiuto.

[Andrea1979]

ti basta cercare

Knapsack Java

su google. Almeno un milione di risultati

[claretta]

Ciao a tutti ho le seguenti classi nel mio programma:

import java.lancs.*;
//import java.lang.Math.*;

public class Test
{      
    
  public static void main(String[] args) throws Exception{


    int [] Weights = {3,8,6,4,2};
    int Values [] = {2,12,9,3,5};
    int Capacity = 9;
    
    Knapsack KS = new Knapsack(Capacity, Weights, Values);
    KS.search(0,0,0);
    System.out.println(KS);
    
    /*
    int [] W = {7,5,4,4,1};    
    Knapsack KS2 = new Knapsack(10,W,W);
    KS2.search(0,0,0);
    System.out.println(KS2);    
    */
 
    /*
    int [] Weights = {3,8,6,4,2,3,8,6,4,2};
    int Values [] = {2,12,9,3,5,2,12,9,3,5};
    int Capacity = 18;
    
    Knapsack KS = new Knapsack(Capacity, Weights, Values);
    KS.search(0,0,0);
    System.out.println(KS);
    */

  }
}

e

public class Knapsack
{

  private int bestValue;
  private int bestWeight;
  private int [] bestSolution;
  private int [] currentSolution;
  private int [] Weight;
  private int [] Value;
  private int Capacity;
  private int numberOfItems;
  private int calls;

  public Knapsack(int c, int [] W, int [] V){
    Capacity = c;
    Weight = W;
    Value = V;
    bestValue = 0;
    numberOfItems = V.length;
    bestSolution = new int[numberOfItems];
    currentSolution = new int[numberOfItems];
    for (int i=0; i<numberOfItems; i++){
      bestSolution[i]=0;
      currentSolution[i]=0;
    }
    calls=0;
  }

  public int getBestValue(){return bestValue;}
  public int [] getBestSolution(){return bestSolution;}
  public int [] getWeight(){return Weight;}
  public int [] getValue(){return Value;}

  private void storeNewBestSolution(){
    for (int i=0;i<numberOfItems;i++)
      bestSolution[i]=currentSolution[i];
  }


  public String toString(){
    String s = "";
    s = s + "\nWeights: ";
    for (int i=0; i<numberOfItems; i++)
      s = s + Weight[i] + " ";
    s = s + "\nValues:  ";
    for (int i=0; i<numberOfItems; i++)
      s = s + Value[i] + " ";
    s = s + "\nTake:    ";
    for (int i=0; i<numberOfItems; i++)
      s = s + bestSolution[i] + " ";
    s = s + "\nCapacity: " + Capacity;
    s = s + "   Weight: " + bestWeight;
    s = s + "   Value: " + bestValue;
    s = s + "   Calls: " + calls;
    return s;
  }  

  private String showCurrent(int depth, int weight, int value){
    String s = "";
    for (int i=0;i<depth;i++)
      s = s + currentSolution[i];
    s = s + "    Weight: " + weight + "  Value: " + value;
    if (value>bestValue && weight<=Capacity)
      s = s + "   *** new best ***";
    return s;
  }
 
  public void search(int depth, int currentWeight, int currentValue){
    calls++;
    System.out.println(showCurrent(depth,currentWeight, currentValue));
    if (currentWeight<=Capacity && currentValue>bestValue){
      bestValue=currentValue;
      bestWeight=currentWeight;
      storeNewBestSolution();
    }
    if (depth<numberOfItems){
      currentSolution[depth]=1; // take, go left
      search(depth+1, currentWeight+Weight[depth],currentValue+Value[depth]);
      currentSolution[depth]=0; // don't take, go right
      search(depth+1, currentWeight, currentValue);
    }
  }
}

Quando compilo la seconda classe nessun problema,quando invece compilo la prima mi da errori.come devo impostare il package in modo che la classe Test possa usare al suo interno la classe Knapsack?

[alka]

Ho unito le discussioni aperte sullo stesso problema.
Non aprire più discussioni sul medesimo argomento; inoltre, usa titoli più significativi.