Discussion :

[utilisateur11]

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 c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

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:



- 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 x :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[pseudocode]

Bonjour,

3 remarques en vrac:

1. L'index pour la création des items (weights[] et values[]) varie entre 0 et n-1.
Mais lors de l'appel de la fonction knapsack(), on passe en paramètre "n" => on va accéder à values[n] et weights[n].
Vraisemblablement, tu devais avoir un truc du genre: take = values[i-1] + knapsack(i-1, ...

2. Il faut toujours évaluer "take" ET "dontTake" pour choisir le meilleur des deux. Dans ton algo, tu évalues l'un OU l'autre.

3. Ce n'est pas un algo dynamique mais un algo d'évaluation récursive: pour calculer knapsack(n) on calcule knapsack(n-1), qui lui même calcule knapsack(n-2), etc.

Dans un algo dynamique on fait une évaluation incrémentale en utilisant les résultats intermédiaires pour calculer le prochain incrément
- knapsack(0) est calculé à partir des données du problème initial.
- knapsack(1) est calculé à partir de knapsack(0) et des données du problème initial.
- knapsack(2) est calculé à partir de knapsack(0), knapsack(1) et des données du problème initial.
- etc.

A+

[utilisateur11]

bien Merci, je vais corriger celà,