Knapsack Problem Fermé

Question

Bonjour,
Salut 
je demande votre aide pour ecrire un programme java concernat l'algorithme fractional Knapsack.
Input:set of"C" item chaque item i dans S a benefit(bi) et weight(wi) maximum total wight Wt.
l'output:Amout pi pour chaque item i qui maximise le total benefit While not exceeding the maximum total weight.
Merci de votre suggestion

Laritta · Answer

SALUT
  volia mon petit programme cocernat le knapsack ecrit en code Java,si quelqu'un trouve des fautes n'hesite pas a me dire 


      import javax.swing.*;
           
   public class Knapsack{
           
              
      static void afficherTab(int [] t){
              
         for(int i=0;i<t.length;i++)
            System.out.println(t[i]+"");
         System.out.println();
      }
   
              
      public static void fractionknapsack(int []b,int [] w,int used[],int Wt)
              
      { int maxi,i;
         int a;
         for( i=0;i<b.length;i++)
         {  used[i] =0;}//I have not used the ith object yet 
      
         int W= 0;
         while(W< Wt)
         {maxi=-1;
            for(i=0;i<b.length;i++)
            { 
               if( ( used[i]==0)&&( (maxi==-1) || ( (float)b[i]/w[i]> (float)b[maxi]/w[maxi]) ))
                  maxi=i;}//Find the best object */ 
         
            int x=Wt-W;
            if(w[maxi]<x)
            {
               a=w[maxi];}
            else { a=x;}
            used[maxi]=a;
            W+=a;
            if(W<Wt)
            
               System.out.println("Added object"+maxi+"("+b[maxi]+","+w[maxi]+") Completly in the bag");}
      }
              
      public static void main(String [] args){
              
         int Wt=Integer.parseInt(JOptionPane.showInputDialog("Donne le maximum total weight SVP"));
         int n=Integer.parseInt(JOptionPane.showInputDialog("Donne le nombre d'item SVP:"));
         int [] used=new int[n];
      
         int [] b=new int [n];
         for(int i=0;i<b.length;i++)
         {b[i]=Integer.parseInt(JOptionPane.showInputDialog("Entrer  le benefit pur l'Item"+i+"SVP"));}
         int [] w=new int [n];
         for(int i=0;i<w.length;i++)
         { w[i]=Integer.parseInt(JOptionPane.showInputDialog("Entrer le weight pur l'Item"+i+"SVP"));}
         System.out.println("tableau des benefit:");
         afficherTab(b);
         System.out.println("Tableau des weight:");
         afficherTab(w);
         fractionknapsack(b,w,used,Wt);
      }
   }