1 pièce(s) jointe(s)
Implémentation d'une solution dynamique au problème du sac-à-dos
Bonjour;
alors dans mon projet fin d'étude, qui n'a aucune relation avec mes études sous nom de sac-à-dos, j'ai besoin de mettre algorithme glouton et algorithme programmation-dynamique pour un problème sac-à-dos'
j'ai travaillé avec un algorithme pré-préparé, donc j'ajoute des truc et je les change... mais j'arrive pas a faire le code qui afficher les objets qui a choisis pour le mettre dans le sac,
j'aimerai des idées qui peuvent m'aidez a avance, sachant que pour mon projet je suis censé apprendre le tout moi même, je n'ai jamais étudié la programmation en c ni en c++, juste la base, mais ça m'aidera pas. Et je ne connais presque sur les 2algo car je les découvre au fil de ces 3mois mais je ne connais que la définition donc voilà :(
je sais que c'est 'interdit' de faire un exercice à la place de quelqu'un, mais j'ai fort besoin de vous, personne ne peut m'aider sauf sur internet
voici mon code, c'est de la programmation dynamique normalement ou du Glouton? ^^
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <iostream>
using namespace std;
#define max(a,b) (a > b ? a : b)
int matrix[100][100] = {0};
bool x[100];
int knapsack(int i, int size, int weights[],int values[]){
int take,dontTake;
take = dontTake = 0;
if (matrix[i][size]!=0)
return matrix[i][size];
if (i==0){
if (weights[0]<=size){
matrix[i][size] = values[0];
return values[0];
}
else{
matrix[i][size] = 0;
return 0;
}
}
if (weights[i]<=size){
take = values[i] + knapsack(i-1, size-weights[i], weights, values);
x[i]=0;}
else {
dontTake = knapsack(i-1, size, weights, values);
x[i]=1;}
cout<< "pour l'objet "<<i<< " , x[i]="<<x[i]<<endl;
matrix[i][size] = max (take, dontTake);
return matrix[i][size];
}
int main(){
int n,knapsackSize,weights[100],values[100];
int i;
cout<<"entrer the number of items"<<endl;
cin>>n;
cout<<"enter the knapsackSize"<<endl;
cin>>knapsackSize;
for(i=0;i<n;i++)
{
cout<<"enter weight and value of item "<<i+1<<endl;
cin>>weights[i]>>values[i];
}
cout<<"Max value ="<<knapsack(n,knapsackSize,weights,values)<<endl;
return 0;
} |
Voici mes questions:
-le code me donne la valeur maximal fausse, ça dois me donner un 90 comme valeur, voici l'exemple que j'ai pris de la programmation dynamique:
Pièce jointe 209727
- j'aimerai savoir c'est quoi la fonction qui permet de me donner les objet choisi a mettre dans le sac
- normalement dans la programmation dynamique: et ce que je dois avoir la matrice ou quoi ? si oui comment le faire, je suis perdu
aidez moi s'il vous plait,
et voici les résulats qui me semble fausse puisque je dois avoir 90comme valeur max.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| entrer the number of items
4
enter the knapsackSize
10
enter weight and value of item 1
5 10
enter weight and value of item 2
4 40
enter weight and value of item 3
6 30
enter weight and value of item 4
3 50
pour l'objet 1 , x[i]=1
pour l'objet 2 , x[i]=0
pour l'objet 3 , x[i]=0
pour l'objet 4 , x[i]=0
Max value =4713208
--------------------------------
Process exited after 22.29 seconds with return value 0
Appuyez sur une touche pour continuer... |
Encore merci.
