Knapsack Problem

Laritta Messages postés 12 Date d'inscription   Statut Membre Dernière intervention   -  
Laritta Messages postés 12 Date d'inscription   Statut Membre Dernière intervention   -
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

1 réponse

Réponse 1 / 1
Laritta Messages postés 12 Date d'inscription   Statut Membre Dernière intervention   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