Knapsack Problem

Laritta Messages postés 12 Statut Membre -  
Laritta Messages postés 12 Statut Membre -
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
Configuration: Windows XP
Internet Explorer 7.0

1 réponse

  1.
    Laritta Messages postés 12 Statut Membre 4
     
    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);
    }
    }
    0