bonjour tout le monde,
Je suis convaincu que le probleme est bien simple (encore une fois ),
je m'explique
Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
pieds, pour realiser une commande ,
Je dois selectionner selon le nombre de verge necessaire les meilleurs
rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
si par exemple jai assez de verge dans un rouleau , ou meme si jai besoin
tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
tout les 6 pieds avant de songer a prendre les 12 pieds)
Mon probleme est dans la selection de multiple rouleau de 12 pieds,
par exemple :
- jai 5 rouleaux de 6 pieds qui donne 200 verges tous ensemble
- jai 4 rouleau de 12 pieds
1 = 100 verges
2 = 125 verges
3 = 106 verges
4 = 200 verges
- pour realiser ma commande jai besoin de 550 verges
donc en theorie je devrais prendre 1-3 et 4 qui sont les plus pres et qui
donne le moin de perte, quel serait l'algo que je devrait utiliser pour
trouver ?
Merci beaucoup a lavance !
Fred
bonjour tout le monde,
Je suis convaincu que le probleme est bien simple (encore une fois ),
je m'explique
Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
pieds, pour realiser une commande ,
Je dois selectionner selon le nombre de verge necessaire les meilleurs
rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
si par exemple jai assez de verge dans un rouleau , ou meme si jai besoin
tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
tout les 6 pieds avant de songer a prendre les 12 pieds)
Mon probleme est dans la selection de multiple rouleau de 12 pieds,
par exemple :
- jai 5 rouleaux de 6 pieds qui donne 200 verges tous ensemble
- jai 4 rouleau de 12 pieds
1 = 100 verges
2 = 125 verges
3 = 106 verges
4 = 200 verges
- pour realiser ma commande jai besoin de 550 verges
donc en theorie je devrais prendre 1-3 et 4 qui sont les plus pres et qui
donne le moin de perte, quel serait l'algo que je devrait utiliser pour
trouver ?
Merci beaucoup a lavance !
Fred
bonjour tout le monde,
Je suis convaincu que le probleme est bien simple (encore une fois ),
je m'explique
Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
pieds, pour realiser une commande ,
Je dois selectionner selon le nombre de verge necessaire les meilleurs
rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
si par exemple jai assez de verge dans un rouleau , ou meme si jai besoin
tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
tout les 6 pieds avant de songer a prendre les 12 pieds)
Mon probleme est dans la selection de multiple rouleau de 12 pieds,
par exemple :
- jai 5 rouleaux de 6 pieds qui donne 200 verges tous ensemble
- jai 4 rouleau de 12 pieds
1 = 100 verges
2 = 125 verges
3 = 106 verges
4 = 200 verges
- pour realiser ma commande jai besoin de 550 verges
donc en theorie je devrais prendre 1-3 et 4 qui sont les plus pres et qui
donne le moin de perte, quel serait l'algo que je devrait utiliser pour
trouver ?
Merci beaucoup a lavance !
Fred
bonjour tout le monde,
Je suis convaincu que le probleme est bien simple (encore une fois ),
je m'explique
Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
pieds, pour realiser une commande ,
Je dois selectionner selon le nombre de verge necessaire les meilleurs
rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
si par exemple jai assez de verge dans un rouleau , ou meme si jai besoin
tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
tout les 6 pieds avant de songer a prendre les 12 pieds)
Mon probleme est dans la selection de multiple rouleau de 12 pieds,
par exemple :
- jai 5 rouleaux de 6 pieds qui donne 200 verges tous ensemble
- jai 4 rouleau de 12 pieds
1 = 100 verges
2 = 125 verges
3 = 106 verges
4 = 200 verges
- pour realiser ma commande jai besoin de 550 verges
donc en theorie je devrais prendre 1-3 et 4 qui sont les plus pres et qui
donne le moin de perte, quel serait l'algo que je devrait utiliser pour
trouver ?
Merci beaucoup a lavance !
Fred
bonjour tout le monde,
Je suis convaincu que le probleme est bien simple (encore une fois ),
je m'explique
Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
pieds, pour realiser une commande ,
Je dois selectionner selon le nombre de verge necessaire les meilleurs
rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
si par exemple jai assez de verge dans un rouleau , ou meme si jai besoin
tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
tout les 6 pieds avant de songer a prendre les 12 pieds)
Mon probleme est dans la selection de multiple rouleau de 12 pieds,
par exemple :
- jai 5 rouleaux de 6 pieds qui donne 200 verges tous ensemble
- jai 4 rouleau de 12 pieds
1 = 100 verges
2 = 125 verges
3 = 106 verges
4 = 200 verges
- pour realiser ma commande jai besoin de 550 verges
donc en theorie je devrais prendre 1-3 et 4 qui sont les plus pres et qui
donne le moin de perte, quel serait l'algo que je devrait utiliser pour
trouver ?
Merci beaucoup a lavance !
Fred
bonjour tout le monde,
Je suis convaincu que le probleme est bien simple (encore une fois ),
je m'explique
Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
pieds, pour realiser une commande ,
Je dois selectionner selon le nombre de verge necessaire les meilleurs
rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
si par exemple jai assez de verge dans un rouleau , ou meme si jai besoin
tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
tout les 6 pieds avant de songer a prendre les 12 pieds)
Mon probleme est dans la selection de multiple rouleau de 12 pieds,
par exemple :
- jai 5 rouleaux de 6 pieds qui donne 200 verges tous ensemble
- jai 4 rouleau de 12 pieds
1 = 100 verges
2 = 125 verges
3 = 106 verges
4 = 200 verges
- pour realiser ma commande jai besoin de 550 verges
donc en theorie je devrais prendre 1-3 et 4 qui sont les plus pres et qui
donne le moin de perte, quel serait l'algo que je devrait utiliser pour
trouver ?
Merci beaucoup a lavance !
Fred
Bonjour,
L'exemple est pas facile à comprendre, surtout quand on ne connaît pas
les verges...
Le principe est de trouver les rouleaux qui seront les plus proche des
découpes dont tu as besoin avec le moins de chutes, alors je dirais une
comparaison en boucle, ou en liste, le problème et qu'il faut quasiment
boucle par rouleau, ça peut être long, il faut faire toutes les
possibles (à 4 tu dois monter dans les 14 combinaisons déjà, espérons que
n'as pas 100 rouleaux <>!!!
Prendre celle la plus proche de la découpe, genre:
3 rouleaux = r(3): les découpes offertes = d(7), taille recherchée= t, bon
rouleaux = b
1ere boucle, charge les possibilités avec les <> rouleaux
1 r1 = d1
2 r2Ò
3 r3Ó
4 r1+r2Ô
5 r1+r3Õ
6 r2+r3Ö
7 r1+r2+r3×
*
b00 'valeur de départ
for i = 1 to 7 ' 2eme boucle cherche la taille > mais la + proche
si d(x) < t exit for ' trop petit
si d(x) > t then et d(x) < b
b=d(x) ' prend à chaque fois le lus proche de 0 (taille requise)
endif
next i
le résultat devrait te donner i=x -> variable(i) = énumérant le n° des
rouleaux à prendre
Je pense que j'y arriverais comme ça, mais ce n'est pas beau, faudrait un
matheux pour te faire un beau truc, le plus grand problème c'est les
imbriquées pour avoir la longueur selon toutes les combinaisons possible,
peu comme faire toutes les combinaisons à 7 chiffres du loto avec les 49
numéros...
--
Merci, @+, bye, Joe
------------------------------------------
Avec une hache, celui qui tient le manche a toujours raison !
------------------------------------------
"Himselff" a écrit dans le message de news:
pGxhc.55193$
> bonjour tout le monde,
>
> Je suis convaincu que le probleme est bien simple (encore une fois ),
voila
> je m'explique
>
> Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
12
> pieds, pour realiser une commande ,
>
> Je dois selectionner selon le nombre de verge necessaire les meilleurs
> rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
faire
> si par exemple jai assez de verge dans un rouleau , ou meme si jai
de
> tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
prendre
> tout les 6 pieds avant de songer a prendre les 12 pieds)
>
> Mon probleme est dans la selection de multiple rouleau de 12 pieds,
>
> par exemple :
>
> - jai 5 rouleaux de 6 pieds qui donne 200 verges tous ensemble
> - jai 4 rouleau de 12 pieds
> 1 = 100 verges
> 2 = 125 verges
> 3 = 106 verges
> 4 = 200 verges
> - pour realiser ma commande jai besoin de 550 verges
>
> donc en theorie je devrais prendre 1-3 et 4 qui sont les plus pres et
> donne le moin de perte, quel serait l'algo que je devrait utiliser pour
les
> trouver ?
>
> Merci beaucoup a lavance !
>
> Fred
>
>
Bonjour,
L'exemple est pas facile à comprendre, surtout quand on ne connaît pas
les verges...
Le principe est de trouver les rouleaux qui seront les plus proche des
découpes dont tu as besoin avec le moins de chutes, alors je dirais une
comparaison en boucle, ou en liste, le problème et qu'il faut quasiment
boucle par rouleau, ça peut être long, il faut faire toutes les
possibles (à 4 tu dois monter dans les 14 combinaisons déjà, espérons que
n'as pas 100 rouleaux <>!!!
Prendre celle la plus proche de la découpe, genre:
3 rouleaux = r(3): les découpes offertes = d(7), taille recherchée= t, bon
rouleaux = b
1ere boucle, charge les possibilités avec les <> rouleaux
1 r1 = d1
2 r2Ò
3 r3Ó
4 r1+r2Ô
5 r1+r3Õ
6 r2+r3Ö
7 r1+r2+r3×
*
b00 'valeur de départ
for i = 1 to 7 ' 2eme boucle cherche la taille > mais la + proche
si d(x) < t exit for ' trop petit
si d(x) > t then et d(x) < b
b=d(x) ' prend à chaque fois le lus proche de 0 (taille requise)
endif
next i
le résultat devrait te donner i=x -> variable(i) = énumérant le n° des
rouleaux à prendre
Je pense que j'y arriverais comme ça, mais ce n'est pas beau, faudrait un
matheux pour te faire un beau truc, le plus grand problème c'est les
imbriquées pour avoir la longueur selon toutes les combinaisons possible,
peu comme faire toutes les combinaisons à 7 chiffres du loto avec les 49
numéros...
--
Merci, @+, bye, Joe
montmartre75@iFrance.com
------------------------------------------
Avec une hache, celui qui tient le manche a toujours raison !
------------------------------------------
"Himselff" <info@dmsinc.ca> a écrit dans le message de news:
pGxhc.55193$Gp4.1267131@news20.bellglobal.com...
> bonjour tout le monde,
>
> Je suis convaincu que le probleme est bien simple (encore une fois ),
voila
> je m'explique
>
> Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
12
> pieds, pour realiser une commande ,
>
> Je dois selectionner selon le nombre de verge necessaire les meilleurs
> rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
faire
> si par exemple jai assez de verge dans un rouleau , ou meme si jai
de
> tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
prendre
> tout les 6 pieds avant de songer a prendre les 12 pieds)
>
> Mon probleme est dans la selection de multiple rouleau de 12 pieds,
>
> par exemple :
>
> - jai 5 rouleaux de 6 pieds qui donne 200 verges tous ensemble
> - jai 4 rouleau de 12 pieds
> 1 = 100 verges
> 2 = 125 verges
> 3 = 106 verges
> 4 = 200 verges
> - pour realiser ma commande jai besoin de 550 verges
>
> donc en theorie je devrais prendre 1-3 et 4 qui sont les plus pres et
> donne le moin de perte, quel serait l'algo que je devrait utiliser pour
les
> trouver ?
>
> Merci beaucoup a lavance !
>
> Fred
>
>
Bonjour,
L'exemple est pas facile à comprendre, surtout quand on ne connaît pas
les verges...
Le principe est de trouver les rouleaux qui seront les plus proche des
découpes dont tu as besoin avec le moins de chutes, alors je dirais une
comparaison en boucle, ou en liste, le problème et qu'il faut quasiment
boucle par rouleau, ça peut être long, il faut faire toutes les
possibles (à 4 tu dois monter dans les 14 combinaisons déjà, espérons que
n'as pas 100 rouleaux <>!!!
Prendre celle la plus proche de la découpe, genre:
3 rouleaux = r(3): les découpes offertes = d(7), taille recherchée= t, bon
rouleaux = b
1ere boucle, charge les possibilités avec les <> rouleaux
1 r1 = d1
2 r2Ò
3 r3Ó
4 r1+r2Ô
5 r1+r3Õ
6 r2+r3Ö
7 r1+r2+r3×
*
b00 'valeur de départ
for i = 1 to 7 ' 2eme boucle cherche la taille > mais la + proche
si d(x) < t exit for ' trop petit
si d(x) > t then et d(x) < b
b=d(x) ' prend à chaque fois le lus proche de 0 (taille requise)
endif
next i
le résultat devrait te donner i=x -> variable(i) = énumérant le n° des
rouleaux à prendre
Je pense que j'y arriverais comme ça, mais ce n'est pas beau, faudrait un
matheux pour te faire un beau truc, le plus grand problème c'est les
imbriquées pour avoir la longueur selon toutes les combinaisons possible,
peu comme faire toutes les combinaisons à 7 chiffres du loto avec les 49
numéros...
--
Merci, @+, bye, Joe
------------------------------------------
Avec une hache, celui qui tient le manche a toujours raison !
------------------------------------------
"Himselff" a écrit dans le message de news:
pGxhc.55193$
> bonjour tout le monde,
>
> Je suis convaincu que le probleme est bien simple (encore une fois ),
voila
> je m'explique
>
> Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
12
> pieds, pour realiser une commande ,
>
> Je dois selectionner selon le nombre de verge necessaire les meilleurs
> rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
faire
> si par exemple jai assez de verge dans un rouleau , ou meme si jai
de
> tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
prendre
> tout les 6 pieds avant de songer a prendre les 12 pieds)
>
> Mon probleme est dans la selection de multiple rouleau de 12 pieds,
>
> par exemple :
>
> - jai 5 rouleaux de 6 pieds qui donne 200 verges tous ensemble
> - jai 4 rouleau de 12 pieds
> 1 = 100 verges
> 2 = 125 verges
> 3 = 106 verges
> 4 = 200 verges
> - pour realiser ma commande jai besoin de 550 verges
>
> donc en theorie je devrais prendre 1-3 et 4 qui sont les plus pres et
> donne le moin de perte, quel serait l'algo que je devrait utiliser pour
les
> trouver ?
>
> Merci beaucoup a lavance !
>
> Fred
>
>
bonjour tout le monde,
Je suis convaincu que le probleme est bien simple (encore une fois ),
je m'explique
Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
pieds, pour realiser une commande ,
Je dois selectionner selon le nombre de verge necessaire les meilleurs
rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
si par exemple jai assez de verge dans un rouleau , ou meme si jai besoin
tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
tout les 6 pieds avant de songer a prendre les 12 pieds)
bonjour tout le monde,
Je suis convaincu que le probleme est bien simple (encore une fois ),
je m'explique
Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
pieds, pour realiser une commande ,
Je dois selectionner selon le nombre de verge necessaire les meilleurs
rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
si par exemple jai assez de verge dans un rouleau , ou meme si jai besoin
tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
tout les 6 pieds avant de songer a prendre les 12 pieds)
bonjour tout le monde,
Je suis convaincu que le probleme est bien simple (encore une fois ),
je m'explique
Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
pieds, pour realiser une commande ,
Je dois selectionner selon le nombre de verge necessaire les meilleurs
rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
si par exemple jai assez de verge dans un rouleau , ou meme si jai besoin
tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
tout les 6 pieds avant de songer a prendre les 12 pieds)
"Himselff" a écrit dans le message de
news:pGxhc.55193$
> bonjour tout le monde,
>
> Je suis convaincu que le probleme est bien simple (encore une fois ),
voila
> je m'explique
>
> Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
12
> pieds, pour realiser une commande ,
>
> Je dois selectionner selon le nombre de verge necessaire les meilleurs
> rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
faire
> si par exemple jai assez de verge dans un rouleau , ou meme si jai
de
> tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
prendre
> tout les 6 pieds avant de songer a prendre les 12 pieds)
Hello,
ce problème n'est pas simple, il est même si compliqué que l'on ne sait
produire une solution optimale en un temps fini. (c'est un problème NP
complet en jargon mathématique).
Ton problème est proche d'un problème générique connu sous le nom de
"programme du sac à dos". Il existe des méthodes de résolution qui
à une solution "la plus optimale possible" en un temps fini.
Tu trouveras une description de ce genre d'algorithme sur google en
cherchant "knapsack problem" ou encore "programmation linéaire" ou encore
"problème du sac à dos".
Les explications et les justifications mathématiques sont un peu (très)
ardues, mais on trouve assez aisément des implémentations de l'algorithme,
en pseudo code ou en C, aisées à traduire en VB.
Jean-Marc
"Himselff" <info@dmsinc.ca> a écrit dans le message de
news:pGxhc.55193$Gp4.1267131@news20.bellglobal.com...
> bonjour tout le monde,
>
> Je suis convaincu que le probleme est bien simple (encore une fois ),
voila
> je m'explique
>
> Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
12
> pieds, pour realiser une commande ,
>
> Je dois selectionner selon le nombre de verge necessaire les meilleurs
> rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
faire
> si par exemple jai assez de verge dans un rouleau , ou meme si jai
de
> tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
prendre
> tout les 6 pieds avant de songer a prendre les 12 pieds)
Hello,
ce problème n'est pas simple, il est même si compliqué que l'on ne sait
produire une solution optimale en un temps fini. (c'est un problème NP
complet en jargon mathématique).
Ton problème est proche d'un problème générique connu sous le nom de
"programme du sac à dos". Il existe des méthodes de résolution qui
à une solution "la plus optimale possible" en un temps fini.
Tu trouveras une description de ce genre d'algorithme sur google en
cherchant "knapsack problem" ou encore "programmation linéaire" ou encore
"problème du sac à dos".
Les explications et les justifications mathématiques sont un peu (très)
ardues, mais on trouve assez aisément des implémentations de l'algorithme,
en pseudo code ou en C, aisées à traduire en VB.
Jean-Marc
"Himselff" a écrit dans le message de
news:pGxhc.55193$
> bonjour tout le monde,
>
> Je suis convaincu que le probleme est bien simple (encore une fois ),
voila
> je m'explique
>
> Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux de
12
> pieds, pour realiser une commande ,
>
> Je dois selectionner selon le nombre de verge necessaire les meilleurs
> rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
faire
> si par exemple jai assez de verge dans un rouleau , ou meme si jai
de
> tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
prendre
> tout les 6 pieds avant de songer a prendre les 12 pieds)
Hello,
ce problème n'est pas simple, il est même si compliqué que l'on ne sait
produire une solution optimale en un temps fini. (c'est un problème NP
complet en jargon mathématique).
Ton problème est proche d'un problème générique connu sous le nom de
"programme du sac à dos". Il existe des méthodes de résolution qui
à une solution "la plus optimale possible" en un temps fini.
Tu trouveras une description de ce genre d'algorithme sur google en
cherchant "knapsack problem" ou encore "programmation linéaire" ou encore
"problème du sac à dos".
Les explications et les justifications mathématiques sont un peu (très)
ardues, mais on trouve assez aisément des implémentations de l'algorithme,
en pseudo code ou en C, aisées à traduire en VB.
Jean-Marc
Wow merci du tuyau , je commence les recherches tout de suite , mais je ne
mattendais pas du tout a avoir a coder un ci gros algo ,
youou moi qui aime les maths en plus =)
souhaiter moi bonne chance =)
Fred
"Jean-Marc" wrote in message
news:4086c373$0$10948$
> "Himselff" a écrit dans le message de
> news:pGxhc.55193$
> > bonjour tout le monde,
> >
> > Je suis convaincu que le probleme est bien simple (encore une fois ),
> voila
> > je m'explique
> >
> > Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux
> 12
> > pieds, pour realiser une commande ,
> >
> > Je dois selectionner selon le nombre de verge necessaire les meilleurs
> > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
> faire
> > si par exemple jai assez de verge dans un rouleau , ou meme si jai
besoin
> de
> > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
> prendre
> > tout les 6 pieds avant de songer a prendre les 12 pieds)
>
> Hello,
> ce problème n'est pas simple, il est même si compliqué que l'on ne sait
pas
> produire une solution optimale en un temps fini. (c'est un problème NP
> complet en jargon mathématique).
>
> Ton problème est proche d'un problème générique connu sous le nom de
> "programme du sac à dos". Il existe des méthodes de résolution qui
arrivent
> à une solution "la plus optimale possible" en un temps fini.
>
> Tu trouveras une description de ce genre d'algorithme sur google en
> cherchant "knapsack problem" ou encore "programmation linéaire" ou
> "problème du sac à dos".
>
> Les explications et les justifications mathématiques sont un peu (très)
> ardues, mais on trouve assez aisément des implémentations de
> en pseudo code ou en C, aisées à traduire en VB.
>
> Jean-Marc
>
>
Wow merci du tuyau , je commence les recherches tout de suite , mais je ne
mattendais pas du tout a avoir a coder un ci gros algo ,
youou moi qui aime les maths en plus =)
souhaiter moi bonne chance =)
Fred
"Jean-Marc" <nospamjean_marc_n2@yahoo.fr> wrote in message
news:4086c373$0$10948$a0ced6e1@news.skynet.be...
> "Himselff" <info@dmsinc.ca> a écrit dans le message de
> news:pGxhc.55193$Gp4.1267131@news20.bellglobal.com...
> > bonjour tout le monde,
> >
> > Je suis convaincu que le probleme est bien simple (encore une fois ),
> voila
> > je m'explique
> >
> > Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux
> 12
> > pieds, pour realiser une commande ,
> >
> > Je dois selectionner selon le nombre de verge necessaire les meilleurs
> > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
> faire
> > si par exemple jai assez de verge dans un rouleau , ou meme si jai
besoin
> de
> > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
> prendre
> > tout les 6 pieds avant de songer a prendre les 12 pieds)
>
> Hello,
> ce problème n'est pas simple, il est même si compliqué que l'on ne sait
pas
> produire une solution optimale en un temps fini. (c'est un problème NP
> complet en jargon mathématique).
>
> Ton problème est proche d'un problème générique connu sous le nom de
> "programme du sac à dos". Il existe des méthodes de résolution qui
arrivent
> à une solution "la plus optimale possible" en un temps fini.
>
> Tu trouveras une description de ce genre d'algorithme sur google en
> cherchant "knapsack problem" ou encore "programmation linéaire" ou
> "problème du sac à dos".
>
> Les explications et les justifications mathématiques sont un peu (très)
> ardues, mais on trouve assez aisément des implémentations de
> en pseudo code ou en C, aisées à traduire en VB.
>
> Jean-Marc
>
>
Wow merci du tuyau , je commence les recherches tout de suite , mais je ne
mattendais pas du tout a avoir a coder un ci gros algo ,
youou moi qui aime les maths en plus =)
souhaiter moi bonne chance =)
Fred
"Jean-Marc" wrote in message
news:4086c373$0$10948$
> "Himselff" a écrit dans le message de
> news:pGxhc.55193$
> > bonjour tout le monde,
> >
> > Je suis convaincu que le probleme est bien simple (encore une fois ),
> voila
> > je m'explique
> >
> > Jai 2 categories de produits les rouleaux de 6 pieds et les rouleaux
> 12
> > pieds, pour realiser une commande ,
> >
> > Je dois selectionner selon le nombre de verge necessaire les meilleurs
> > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a le
> faire
> > si par exemple jai assez de verge dans un rouleau , ou meme si jai
besoin
> de
> > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
> prendre
> > tout les 6 pieds avant de songer a prendre les 12 pieds)
>
> Hello,
> ce problème n'est pas simple, il est même si compliqué que l'on ne sait
pas
> produire une solution optimale en un temps fini. (c'est un problème NP
> complet en jargon mathématique).
>
> Ton problème est proche d'un problème générique connu sous le nom de
> "programme du sac à dos". Il existe des méthodes de résolution qui
arrivent
> à une solution "la plus optimale possible" en un temps fini.
>
> Tu trouveras une description de ce genre d'algorithme sur google en
> cherchant "knapsack problem" ou encore "programmation linéaire" ou
> "problème du sac à dos".
>
> Les explications et les justifications mathématiques sont un peu (très)
> ardues, mais on trouve assez aisément des implémentations de
> en pseudo code ou en C, aisées à traduire en VB.
>
> Jean-Marc
>
>
> Avant de me lancer plus avant, que viennent faire les rouleaux de 6 pieds
dans ce pb ?
J'ai traité ce genre de problème sur ce forum il y a quelques temps : il
fallait trouver la "meilleure" façon de réaliser une somme avec
pièces. Ici il s'agit de réaliser de la meilleure façon une longueur avec
différents rouleaux de certaines longueurs chacun.
On trouve l'explication de l'algorithme correspondant dans Structure te
interprétation des programmes informatiques de Abelson et Sussman (exemple
du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
édition en anglais est disponible en ligne. [on peut télécharger son pdf],
http://deptinfo.unice.fr/~roy/sicp.pdf)
Il s'agit d'un algo récursif ce qui évite l'emploi de for next imbriqué et
est plus compréhensible.
Avant de me lancer plus avant, que viennent faire les rouleaux de 6 pieds
dans ce pb ?
En tout cas voici ce que ça donne avec les pièces de monnaies.
Example: Counting change
It takes only a bit of cleverness to come up with the iterative Fibonacci
algorithm. In contrast, consider the
following problem: How many different ways can we make change of $ 1.00,
given half-dollars, quarters,
dimes, nickels, and pennies? More generally, can we write a procedure to
compute the number of ways to
change any given amount of money?
This problem has a simple solution as a recursive procedure. Suppose we
think of the types of coins
available as arranged in some order. Then the following relation holds:
The number of ways to change amount a using n kinds of coins equals
the number of ways to change amount a using all but the first kind of
plus
the number of ways to change amount a - d using all n kinds of coins,
d is the denomination
of the first kind of coin.
To see why this is true, observe that the ways to make change can be
into two groups: those that
do not use any of the first kind of coin, and those that do. Therefore,
total number of ways to make
change for some amount is equal to the number of ways to make change for
amount without using any
of the first kind of coin, plus the number of ways to make change assuming
that we do use the first kind of
coin. But the latter number is equal to the number of ways to make change
for the amount that remains
after using a coin of the first kind.
Thus, we can recursively reduce the problem of changing a given amount to
the problem of changing
smaller amounts using fewer kinds of coins. Consider this reduction rule
carefully, and convince yourself
that we can use it to describe an algorithm if we specify the following
degenerate cases:
If a is exactly 0, we should count that as 1 way to make change.
If a is less than 0, we should count that as 0 ways to make change.
If n is 0, we should count that as 0 ways to make change.
We can easily translate this description into a recursive procedure:
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(The first-denomination procedure takes as input the number of kinds of
coins available and
returns the denomination of the first kind. Here we are thinking of the
coins as arranged in order from
largest to smallest, but any order would do as well.) We can now answer
original question about
changing a dollar:
(count-change 100)
Count-change generates a tree-recursive process with redundancies similar
those in our first
implementation of fib. (It will take quite a while for that 292 to be
computed.) On the other hand, it is
not obvious how to design a better algorithm for computing the result, and
we leave this problem as a
challenge. The observation that a tree-recursive process may be highly
inefficient but often easy to specify
and understand has led people to propose that one could get the best of
worlds by designing a ``smart
compiler'' that could transform tree-recursive procedures into more
efficient procedures that compute the
same result.
Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je peux
t'aider dans ce projet.
En gros on part de l'idée que si f est une fonction permettant d'atteindre
avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
J'ai l'impression que la première réponse avec problème NP évoquait plutôt
celui du plus court chemin en passant par des points obligés. Le fait
en dimension deux change beaucoup le pb.
"Himselff" a écrit dans le message de
news:KNzhc.57140$
> Wow merci du tuyau , je commence les recherches tout de suite , mais je
> mattendais pas du tout a avoir a coder un ci gros algo ,
>
> youou moi qui aime les maths en plus =)
>
> souhaiter moi bonne chance =)
>
> Fred
>
> "Jean-Marc" wrote in message
> news:4086c373$0$10948$
> > "Himselff" a écrit dans le message de
> > news:pGxhc.55193$
> > > bonjour tout le monde,
> > >
> > > Je suis convaincu que le probleme est bien simple (encore une
> > voila
> > > je m'explique
> > >
> > > Jai 2 categories de produits les rouleaux de 6 pieds et les
de
> > 12
> > > pieds, pour realiser une commande ,
> > >
> > > Je dois selectionner selon le nombre de verge necessaire les
> > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a
> > faire
> > > si par exemple jai assez de verge dans un rouleau , ou meme si jai
> besoin
> > de
> > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
> > prendre
> > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> >
> > Hello,
> > ce problème n'est pas simple, il est même si compliqué que l'on ne
> pas
> > produire une solution optimale en un temps fini. (c'est un problème NP
> > complet en jargon mathématique).
> >
> > Ton problème est proche d'un problème générique connu sous le nom de
> > "programme du sac à dos". Il existe des méthodes de résolution qui
> arrivent
> > à une solution "la plus optimale possible" en un temps fini.
> >
> > Tu trouveras une description de ce genre d'algorithme sur google en
> > cherchant "knapsack problem" ou encore "programmation linéaire" ou
encore
> > "problème du sac à dos".
> >
> > Les explications et les justifications mathématiques sont un peu
> > ardues, mais on trouve assez aisément des implémentations de
l'algorithme,
> > en pseudo code ou en C, aisées à traduire en VB.
> >
> > Jean-Marc
> >
> >
>
>
> Avant de me lancer plus avant, que viennent faire les rouleaux de 6 pieds
dans ce pb ?
J'ai traité ce genre de problème sur ce forum il y a quelques temps : il
fallait trouver la "meilleure" façon de réaliser une somme avec
pièces. Ici il s'agit de réaliser de la meilleure façon une longueur avec
différents rouleaux de certaines longueurs chacun.
On trouve l'explication de l'algorithme correspondant dans Structure te
interprétation des programmes informatiques de Abelson et Sussman (exemple
du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
édition en anglais est disponible en ligne. [on peut télécharger son pdf],
http://deptinfo.unice.fr/~roy/sicp.pdf)
Il s'agit d'un algo récursif ce qui évite l'emploi de for next imbriqué et
est plus compréhensible.
Avant de me lancer plus avant, que viennent faire les rouleaux de 6 pieds
dans ce pb ?
En tout cas voici ce que ça donne avec les pièces de monnaies.
Example: Counting change
It takes only a bit of cleverness to come up with the iterative Fibonacci
algorithm. In contrast, consider the
following problem: How many different ways can we make change of $ 1.00,
given half-dollars, quarters,
dimes, nickels, and pennies? More generally, can we write a procedure to
compute the number of ways to
change any given amount of money?
This problem has a simple solution as a recursive procedure. Suppose we
think of the types of coins
available as arranged in some order. Then the following relation holds:
The number of ways to change amount a using n kinds of coins equals
the number of ways to change amount a using all but the first kind of
plus
the number of ways to change amount a - d using all n kinds of coins,
d is the denomination
of the first kind of coin.
To see why this is true, observe that the ways to make change can be
into two groups: those that
do not use any of the first kind of coin, and those that do. Therefore,
total number of ways to make
change for some amount is equal to the number of ways to make change for
amount without using any
of the first kind of coin, plus the number of ways to make change assuming
that we do use the first kind of
coin. But the latter number is equal to the number of ways to make change
for the amount that remains
after using a coin of the first kind.
Thus, we can recursively reduce the problem of changing a given amount to
the problem of changing
smaller amounts using fewer kinds of coins. Consider this reduction rule
carefully, and convince yourself
that we can use it to describe an algorithm if we specify the following
degenerate cases:
If a is exactly 0, we should count that as 1 way to make change.
If a is less than 0, we should count that as 0 ways to make change.
If n is 0, we should count that as 0 ways to make change.
We can easily translate this description into a recursive procedure:
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(The first-denomination procedure takes as input the number of kinds of
coins available and
returns the denomination of the first kind. Here we are thinking of the
coins as arranged in order from
largest to smallest, but any order would do as well.) We can now answer
original question about
changing a dollar:
(count-change 100)
Count-change generates a tree-recursive process with redundancies similar
those in our first
implementation of fib. (It will take quite a while for that 292 to be
computed.) On the other hand, it is
not obvious how to design a better algorithm for computing the result, and
we leave this problem as a
challenge. The observation that a tree-recursive process may be highly
inefficient but often easy to specify
and understand has led people to propose that one could get the best of
worlds by designing a ``smart
compiler'' that could transform tree-recursive procedures into more
efficient procedures that compute the
same result.
Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je peux
t'aider dans ce projet.
En gros on part de l'idée que si f est une fonction permettant d'atteindre
avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
J'ai l'impression que la première réponse avec problème NP évoquait plutôt
celui du plus court chemin en passant par des points obligés. Le fait
en dimension deux change beaucoup le pb.
"Himselff" <info@dmsinc.ca> a écrit dans le message de
news:KNzhc.57140$Gp4.1302111@news20.bellglobal.com...
> Wow merci du tuyau , je commence les recherches tout de suite , mais je
> mattendais pas du tout a avoir a coder un ci gros algo ,
>
> youou moi qui aime les maths en plus =)
>
> souhaiter moi bonne chance =)
>
> Fred
>
> "Jean-Marc" <nospamjean_marc_n2@yahoo.fr> wrote in message
> news:4086c373$0$10948$a0ced6e1@news.skynet.be...
> > "Himselff" <info@dmsinc.ca> a écrit dans le message de
> > news:pGxhc.55193$Gp4.1267131@news20.bellglobal.com...
> > > bonjour tout le monde,
> > >
> > > Je suis convaincu que le probleme est bien simple (encore une
> > voila
> > > je m'explique
> > >
> > > Jai 2 categories de produits les rouleaux de 6 pieds et les
de
> > 12
> > > pieds, pour realiser une commande ,
> > >
> > > Je dois selectionner selon le nombre de verge necessaire les
> > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a
> > faire
> > > si par exemple jai assez de verge dans un rouleau , ou meme si jai
> besoin
> > de
> > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
> > prendre
> > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> >
> > Hello,
> > ce problème n'est pas simple, il est même si compliqué que l'on ne
> pas
> > produire une solution optimale en un temps fini. (c'est un problème NP
> > complet en jargon mathématique).
> >
> > Ton problème est proche d'un problème générique connu sous le nom de
> > "programme du sac à dos". Il existe des méthodes de résolution qui
> arrivent
> > à une solution "la plus optimale possible" en un temps fini.
> >
> > Tu trouveras une description de ce genre d'algorithme sur google en
> > cherchant "knapsack problem" ou encore "programmation linéaire" ou
encore
> > "problème du sac à dos".
> >
> > Les explications et les justifications mathématiques sont un peu
> > ardues, mais on trouve assez aisément des implémentations de
l'algorithme,
> > en pseudo code ou en C, aisées à traduire en VB.
> >
> > Jean-Marc
> >
> >
>
>
> Avant de me lancer plus avant, que viennent faire les rouleaux de 6 pieds
dans ce pb ?
J'ai traité ce genre de problème sur ce forum il y a quelques temps : il
fallait trouver la "meilleure" façon de réaliser une somme avec
pièces. Ici il s'agit de réaliser de la meilleure façon une longueur avec
différents rouleaux de certaines longueurs chacun.
On trouve l'explication de l'algorithme correspondant dans Structure te
interprétation des programmes informatiques de Abelson et Sussman (exemple
du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
édition en anglais est disponible en ligne. [on peut télécharger son pdf],
http://deptinfo.unice.fr/~roy/sicp.pdf)
Il s'agit d'un algo récursif ce qui évite l'emploi de for next imbriqué et
est plus compréhensible.
Avant de me lancer plus avant, que viennent faire les rouleaux de 6 pieds
dans ce pb ?
En tout cas voici ce que ça donne avec les pièces de monnaies.
Example: Counting change
It takes only a bit of cleverness to come up with the iterative Fibonacci
algorithm. In contrast, consider the
following problem: How many different ways can we make change of $ 1.00,
given half-dollars, quarters,
dimes, nickels, and pennies? More generally, can we write a procedure to
compute the number of ways to
change any given amount of money?
This problem has a simple solution as a recursive procedure. Suppose we
think of the types of coins
available as arranged in some order. Then the following relation holds:
The number of ways to change amount a using n kinds of coins equals
the number of ways to change amount a using all but the first kind of
plus
the number of ways to change amount a - d using all n kinds of coins,
d is the denomination
of the first kind of coin.
To see why this is true, observe that the ways to make change can be
into two groups: those that
do not use any of the first kind of coin, and those that do. Therefore,
total number of ways to make
change for some amount is equal to the number of ways to make change for
amount without using any
of the first kind of coin, plus the number of ways to make change assuming
that we do use the first kind of
coin. But the latter number is equal to the number of ways to make change
for the amount that remains
after using a coin of the first kind.
Thus, we can recursively reduce the problem of changing a given amount to
the problem of changing
smaller amounts using fewer kinds of coins. Consider this reduction rule
carefully, and convince yourself
that we can use it to describe an algorithm if we specify the following
degenerate cases:
If a is exactly 0, we should count that as 1 way to make change.
If a is less than 0, we should count that as 0 ways to make change.
If n is 0, we should count that as 0 ways to make change.
We can easily translate this description into a recursive procedure:
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(The first-denomination procedure takes as input the number of kinds of
coins available and
returns the denomination of the first kind. Here we are thinking of the
coins as arranged in order from
largest to smallest, but any order would do as well.) We can now answer
original question about
changing a dollar:
(count-change 100)
Count-change generates a tree-recursive process with redundancies similar
those in our first
implementation of fib. (It will take quite a while for that 292 to be
computed.) On the other hand, it is
not obvious how to design a better algorithm for computing the result, and
we leave this problem as a
challenge. The observation that a tree-recursive process may be highly
inefficient but often easy to specify
and understand has led people to propose that one could get the best of
worlds by designing a ``smart
compiler'' that could transform tree-recursive procedures into more
efficient procedures that compute the
same result.
Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je peux
t'aider dans ce projet.
En gros on part de l'idée que si f est une fonction permettant d'atteindre
avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
J'ai l'impression que la première réponse avec problème NP évoquait plutôt
celui du plus court chemin en passant par des points obligés. Le fait
en dimension deux change beaucoup le pb.
"Himselff" a écrit dans le message de
news:KNzhc.57140$
> Wow merci du tuyau , je commence les recherches tout de suite , mais je
> mattendais pas du tout a avoir a coder un ci gros algo ,
>
> youou moi qui aime les maths en plus =)
>
> souhaiter moi bonne chance =)
>
> Fred
>
> "Jean-Marc" wrote in message
> news:4086c373$0$10948$
> > "Himselff" a écrit dans le message de
> > news:pGxhc.55193$
> > > bonjour tout le monde,
> > >
> > > Je suis convaincu que le probleme est bien simple (encore une
> > voila
> > > je m'explique
> > >
> > > Jai 2 categories de produits les rouleaux de 6 pieds et les
de
> > 12
> > > pieds, pour realiser une commande ,
> > >
> > > Je dois selectionner selon le nombre de verge necessaire les
> > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a
> > faire
> > > si par exemple jai assez de verge dans un rouleau , ou meme si jai
> besoin
> > de
> > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
> > prendre
> > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> >
> > Hello,
> > ce problème n'est pas simple, il est même si compliqué que l'on ne
> pas
> > produire une solution optimale en un temps fini. (c'est un problème NP
> > complet en jargon mathématique).
> >
> > Ton problème est proche d'un problème générique connu sous le nom de
> > "programme du sac à dos". Il existe des méthodes de résolution qui
> arrivent
> > à une solution "la plus optimale possible" en un temps fini.
> >
> > Tu trouveras une description de ce genre d'algorithme sur google en
> > cherchant "knapsack problem" ou encore "programmation linéaire" ou
encore
> > "problème du sac à dos".
> >
> > Les explications et les justifications mathématiques sont un peu
> > ardues, mais on trouve assez aisément des implémentations de
l'algorithme,
> > en pseudo code ou en C, aisées à traduire en VB.
> >
> > Jean-Marc
> >
> >
>
>
J'ai traité ce genre de problème sur ce forum il y a quelques temps : il
fallait trouver la "meilleure" façon de réaliser une somme avec
pièces. Ici il s'agit de réaliser de la meilleure façon une longueur avec
différents rouleaux de certaines longueurs chacun.
On trouve l'explication de l'algorithme correspondant dans Structure te
interprétation des programmes informatiques de Abelson et Sussman (exemple
du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
édition en anglais est disponible en ligne. [on peut télécharger son pdf],
http://deptinfo.unice.fr/~roy/sicp.pdf)
Il s'agit d'un algo récursif ce qui évite l'emploi de for next imbriqué et
est plus compréhensible.
Avant de me lancer plus avant, que viennent faire les rouleaux de 6 pieds
dans ce pb ?
En tout cas voici ce que ça donne avec les pièces de monnaies.
Example: Counting change
It takes only a bit of cleverness to come up with the iterative Fibonacci
algorithm. In contrast, consider the
following problem: How many different ways can we make change of $ 1.00,
given half-dollars, quarters,
dimes, nickels, and pennies? More generally, can we write a procedure to
compute the number of ways to
change any given amount of money?
This problem has a simple solution as a recursive procedure. Suppose we
think of the types of coins
available as arranged in some order. Then the following relation holds:
The number of ways to change amount a using n kinds of coins equals
the number of ways to change amount a using all but the first kind of
plus
the number of ways to change amount a - d using all n kinds of coins,
d is the denomination
of the first kind of coin.
To see why this is true, observe that the ways to make change can be
into two groups: those that
do not use any of the first kind of coin, and those that do. Therefore,
total number of ways to make
change for some amount is equal to the number of ways to make change for
amount without using any
of the first kind of coin, plus the number of ways to make change assuming
that we do use the first kind of
coin. But the latter number is equal to the number of ways to make change
for the amount that remains
after using a coin of the first kind.
Thus, we can recursively reduce the problem of changing a given amount to
the problem of changing
smaller amounts using fewer kinds of coins. Consider this reduction rule
carefully, and convince yourself
that we can use it to describe an algorithm if we specify the following
degenerate cases:
If a is exactly 0, we should count that as 1 way to make change.
If a is less than 0, we should count that as 0 ways to make change.
If n is 0, we should count that as 0 ways to make change.
We can easily translate this description into a recursive procedure:
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(The first-denomination procedure takes as input the number of kinds of
coins available and
returns the denomination of the first kind. Here we are thinking of the
coins as arranged in order from
largest to smallest, but any order would do as well.) We can now answer
original question about
changing a dollar:
(count-change 100)
Count-change generates a tree-recursive process with redundancies similar
those in our first
implementation of fib. (It will take quite a while for that 292 to be
computed.) On the other hand, it is
not obvious how to design a better algorithm for computing the result, and
we leave this problem as a
challenge. The observation that a tree-recursive process may be highly
inefficient but often easy to specify
and understand has led people to propose that one could get the best of
worlds by designing a ``smart
compiler'' that could transform tree-recursive procedures into more
efficient procedures that compute the
same result.
Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je peux
t'aider dans ce projet.
En gros on part de l'idée que si f est une fonction permettant d'atteindre
avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
J'ai l'impression que la première réponse avec problème NP évoquait plutôt
celui du plus court chemin en passant par des points obligés. Le fait
en dimension deux change beaucoup le pb.
"Himselff" a écrit dans le message de
news:KNzhc.57140$
> Wow merci du tuyau , je commence les recherches tout de suite , mais je
> mattendais pas du tout a avoir a coder un ci gros algo ,
>
> youou moi qui aime les maths en plus =)
>
> souhaiter moi bonne chance =)
>
> Fred
>
> "Jean-Marc" wrote in message
> news:4086c373$0$10948$
> > "Himselff" a écrit dans le message de
> > news:pGxhc.55193$
> > > bonjour tout le monde,
> > >
> > > Je suis convaincu que le probleme est bien simple (encore une
> > voila
> > > je m'explique
> > >
> > > Jai 2 categories de produits les rouleaux de 6 pieds et les
de
> > 12
> > > pieds, pour realiser une commande ,
> > >
> > > Je dois selectionner selon le nombre de verge necessaire les
> > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a
> > faire
> > > si par exemple jai assez de verge dans un rouleau , ou meme si jai
> besoin
> > de
> > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
> > prendre
> > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> >
> > Hello,
> > ce problème n'est pas simple, il est même si compliqué que l'on ne
> pas
> > produire une solution optimale en un temps fini. (c'est un problème NP
> > complet en jargon mathématique).
> >
> > Ton problème est proche d'un problème générique connu sous le nom de
> > "programme du sac à dos". Il existe des méthodes de résolution qui
> arrivent
> > à une solution "la plus optimale possible" en un temps fini.
> >
> > Tu trouveras une description de ce genre d'algorithme sur google en
> > cherchant "knapsack problem" ou encore "programmation linéaire" ou
encore
> > "problème du sac à dos".
> >
> > Les explications et les justifications mathématiques sont un peu
> > ardues, mais on trouve assez aisément des implémentations de
l'algorithme,
> > en pseudo code ou en C, aisées à traduire en VB.
> >
> > Jean-Marc
> >
> >
>
>
J'ai traité ce genre de problème sur ce forum il y a quelques temps : il
fallait trouver la "meilleure" façon de réaliser une somme avec
pièces. Ici il s'agit de réaliser de la meilleure façon une longueur avec
différents rouleaux de certaines longueurs chacun.
On trouve l'explication de l'algorithme correspondant dans Structure te
interprétation des programmes informatiques de Abelson et Sussman (exemple
du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
édition en anglais est disponible en ligne. [on peut télécharger son pdf],
http://deptinfo.unice.fr/~roy/sicp.pdf)
Il s'agit d'un algo récursif ce qui évite l'emploi de for next imbriqué et
est plus compréhensible.
Avant de me lancer plus avant, que viennent faire les rouleaux de 6 pieds
dans ce pb ?
En tout cas voici ce que ça donne avec les pièces de monnaies.
Example: Counting change
It takes only a bit of cleverness to come up with the iterative Fibonacci
algorithm. In contrast, consider the
following problem: How many different ways can we make change of $ 1.00,
given half-dollars, quarters,
dimes, nickels, and pennies? More generally, can we write a procedure to
compute the number of ways to
change any given amount of money?
This problem has a simple solution as a recursive procedure. Suppose we
think of the types of coins
available as arranged in some order. Then the following relation holds:
The number of ways to change amount a using n kinds of coins equals
the number of ways to change amount a using all but the first kind of
plus
the number of ways to change amount a - d using all n kinds of coins,
d is the denomination
of the first kind of coin.
To see why this is true, observe that the ways to make change can be
into two groups: those that
do not use any of the first kind of coin, and those that do. Therefore,
total number of ways to make
change for some amount is equal to the number of ways to make change for
amount without using any
of the first kind of coin, plus the number of ways to make change assuming
that we do use the first kind of
coin. But the latter number is equal to the number of ways to make change
for the amount that remains
after using a coin of the first kind.
Thus, we can recursively reduce the problem of changing a given amount to
the problem of changing
smaller amounts using fewer kinds of coins. Consider this reduction rule
carefully, and convince yourself
that we can use it to describe an algorithm if we specify the following
degenerate cases:
If a is exactly 0, we should count that as 1 way to make change.
If a is less than 0, we should count that as 0 ways to make change.
If n is 0, we should count that as 0 ways to make change.
We can easily translate this description into a recursive procedure:
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(The first-denomination procedure takes as input the number of kinds of
coins available and
returns the denomination of the first kind. Here we are thinking of the
coins as arranged in order from
largest to smallest, but any order would do as well.) We can now answer
original question about
changing a dollar:
(count-change 100)
Count-change generates a tree-recursive process with redundancies similar
those in our first
implementation of fib. (It will take quite a while for that 292 to be
computed.) On the other hand, it is
not obvious how to design a better algorithm for computing the result, and
we leave this problem as a
challenge. The observation that a tree-recursive process may be highly
inefficient but often easy to specify
and understand has led people to propose that one could get the best of
worlds by designing a ``smart
compiler'' that could transform tree-recursive procedures into more
efficient procedures that compute the
same result.
Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je peux
t'aider dans ce projet.
En gros on part de l'idée que si f est une fonction permettant d'atteindre
avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
J'ai l'impression que la première réponse avec problème NP évoquait plutôt
celui du plus court chemin en passant par des points obligés. Le fait
en dimension deux change beaucoup le pb.
"Himselff" <info@dmsinc.ca> a écrit dans le message de
news:KNzhc.57140$Gp4.1302111@news20.bellglobal.com...
> Wow merci du tuyau , je commence les recherches tout de suite , mais je
> mattendais pas du tout a avoir a coder un ci gros algo ,
>
> youou moi qui aime les maths en plus =)
>
> souhaiter moi bonne chance =)
>
> Fred
>
> "Jean-Marc" <nospamjean_marc_n2@yahoo.fr> wrote in message
> news:4086c373$0$10948$a0ced6e1@news.skynet.be...
> > "Himselff" <info@dmsinc.ca> a écrit dans le message de
> > news:pGxhc.55193$Gp4.1267131@news20.bellglobal.com...
> > > bonjour tout le monde,
> > >
> > > Je suis convaincu que le probleme est bien simple (encore une
> > voila
> > > je m'explique
> > >
> > > Jai 2 categories de produits les rouleaux de 6 pieds et les
de
> > 12
> > > pieds, pour realiser une commande ,
> > >
> > > Je dois selectionner selon le nombre de verge necessaire les
> > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a
> > faire
> > > si par exemple jai assez de verge dans un rouleau , ou meme si jai
> besoin
> > de
> > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
> > prendre
> > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> >
> > Hello,
> > ce problème n'est pas simple, il est même si compliqué que l'on ne
> pas
> > produire une solution optimale en un temps fini. (c'est un problème NP
> > complet en jargon mathématique).
> >
> > Ton problème est proche d'un problème générique connu sous le nom de
> > "programme du sac à dos". Il existe des méthodes de résolution qui
> arrivent
> > à une solution "la plus optimale possible" en un temps fini.
> >
> > Tu trouveras une description de ce genre d'algorithme sur google en
> > cherchant "knapsack problem" ou encore "programmation linéaire" ou
encore
> > "problème du sac à dos".
> >
> > Les explications et les justifications mathématiques sont un peu
> > ardues, mais on trouve assez aisément des implémentations de
l'algorithme,
> > en pseudo code ou en C, aisées à traduire en VB.
> >
> > Jean-Marc
> >
> >
>
>
J'ai traité ce genre de problème sur ce forum il y a quelques temps : il
fallait trouver la "meilleure" façon de réaliser une somme avec
pièces. Ici il s'agit de réaliser de la meilleure façon une longueur avec
différents rouleaux de certaines longueurs chacun.
On trouve l'explication de l'algorithme correspondant dans Structure te
interprétation des programmes informatiques de Abelson et Sussman (exemple
du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
édition en anglais est disponible en ligne. [on peut télécharger son pdf],
http://deptinfo.unice.fr/~roy/sicp.pdf)
Il s'agit d'un algo récursif ce qui évite l'emploi de for next imbriqué et
est plus compréhensible.
Avant de me lancer plus avant, que viennent faire les rouleaux de 6 pieds
dans ce pb ?
En tout cas voici ce que ça donne avec les pièces de monnaies.
Example: Counting change
It takes only a bit of cleverness to come up with the iterative Fibonacci
algorithm. In contrast, consider the
following problem: How many different ways can we make change of $ 1.00,
given half-dollars, quarters,
dimes, nickels, and pennies? More generally, can we write a procedure to
compute the number of ways to
change any given amount of money?
This problem has a simple solution as a recursive procedure. Suppose we
think of the types of coins
available as arranged in some order. Then the following relation holds:
The number of ways to change amount a using n kinds of coins equals
the number of ways to change amount a using all but the first kind of
plus
the number of ways to change amount a - d using all n kinds of coins,
d is the denomination
of the first kind of coin.
To see why this is true, observe that the ways to make change can be
into two groups: those that
do not use any of the first kind of coin, and those that do. Therefore,
total number of ways to make
change for some amount is equal to the number of ways to make change for
amount without using any
of the first kind of coin, plus the number of ways to make change assuming
that we do use the first kind of
coin. But the latter number is equal to the number of ways to make change
for the amount that remains
after using a coin of the first kind.
Thus, we can recursively reduce the problem of changing a given amount to
the problem of changing
smaller amounts using fewer kinds of coins. Consider this reduction rule
carefully, and convince yourself
that we can use it to describe an algorithm if we specify the following
degenerate cases:
If a is exactly 0, we should count that as 1 way to make change.
If a is less than 0, we should count that as 0 ways to make change.
If n is 0, we should count that as 0 ways to make change.
We can easily translate this description into a recursive procedure:
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(The first-denomination procedure takes as input the number of kinds of
coins available and
returns the denomination of the first kind. Here we are thinking of the
coins as arranged in order from
largest to smallest, but any order would do as well.) We can now answer
original question about
changing a dollar:
(count-change 100)
Count-change generates a tree-recursive process with redundancies similar
those in our first
implementation of fib. (It will take quite a while for that 292 to be
computed.) On the other hand, it is
not obvious how to design a better algorithm for computing the result, and
we leave this problem as a
challenge. The observation that a tree-recursive process may be highly
inefficient but often easy to specify
and understand has led people to propose that one could get the best of
worlds by designing a ``smart
compiler'' that could transform tree-recursive procedures into more
efficient procedures that compute the
same result.
Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je peux
t'aider dans ce projet.
En gros on part de l'idée que si f est une fonction permettant d'atteindre
avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
J'ai l'impression que la première réponse avec problème NP évoquait plutôt
celui du plus court chemin en passant par des points obligés. Le fait
en dimension deux change beaucoup le pb.
"Himselff" a écrit dans le message de
news:KNzhc.57140$
> Wow merci du tuyau , je commence les recherches tout de suite , mais je
> mattendais pas du tout a avoir a coder un ci gros algo ,
>
> youou moi qui aime les maths en plus =)
>
> souhaiter moi bonne chance =)
>
> Fred
>
> "Jean-Marc" wrote in message
> news:4086c373$0$10948$
> > "Himselff" a écrit dans le message de
> > news:pGxhc.55193$
> > > bonjour tout le monde,
> > >
> > > Je suis convaincu que le probleme est bien simple (encore une
> > voila
> > > je m'explique
> > >
> > > Jai 2 categories de produits les rouleaux de 6 pieds et les
de
> > 12
> > > pieds, pour realiser une commande ,
> > >
> > > Je dois selectionner selon le nombre de verge necessaire les
> > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a
> > faire
> > > si par exemple jai assez de verge dans un rouleau , ou meme si jai
> besoin
> > de
> > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je dois
> > prendre
> > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> >
> > Hello,
> > ce problème n'est pas simple, il est même si compliqué que l'on ne
> pas
> > produire une solution optimale en un temps fini. (c'est un problème NP
> > complet en jargon mathématique).
> >
> > Ton problème est proche d'un problème générique connu sous le nom de
> > "programme du sac à dos". Il existe des méthodes de résolution qui
> arrivent
> > à une solution "la plus optimale possible" en un temps fini.
> >
> > Tu trouveras une description de ce genre d'algorithme sur google en
> > cherchant "knapsack problem" ou encore "programmation linéaire" ou
encore
> > "problème du sac à dos".
> >
> > Les explications et les justifications mathématiques sont un peu
> > ardues, mais on trouve assez aisément des implémentations de
l'algorithme,
> > en pseudo code ou en C, aisées à traduire en VB.
> >
> > Jean-Marc
> >
> >
>
>
La récursivité, je ne sais pas si c'est une bonne solution, car je crois
ça ne dépile pas contrairement à une boucle, alors faut voir si on ne
pas de sortir en "fin de pile", juste une petite réflexion
Appeler une autre fonction, çan doit dépiler (end...), mais appeler sa
propre fonction, pas certain que ça dépile avant la fin du traitement...
--
Merci, @+, bye, Joe
------------------------------------------
Avec une hache, celui qui tient le manche a toujours raison !
------------------------------------------
"Patrice Henrio" a écrit dans le
message de news:
> J'ai traité ce genre de problème sur ce forum il y a quelques temps : il
> fallait trouver la "meilleure" façon de réaliser une somme avec
différentes
> pièces. Ici il s'agit de réaliser de la meilleure façon une longueur
> différents rouleaux de certaines longueurs chacun.
> On trouve l'explication de l'algorithme correspondant dans Structure te
> interprétation des programmes informatiques de Abelson et Sussman
> du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
> édition en anglais est disponible en ligne. [on peut télécharger son
> http://deptinfo.unice.fr/~roy/sicp.pdf)
> Il s'agit d'un algo récursif ce qui évite l'emploi de for next imbriqué
> est plus compréhensible.
> Avant de me lancer plus avant, que viennent faire les rouleaux de 6
> dans ce pb ?
> En tout cas voici ce que ça donne avec les pièces de monnaies.
> Example: Counting change
> It takes only a bit of cleverness to come up with the iterative
> algorithm. In contrast, consider the
> following problem: How many different ways can we make change of $ 1.00,
> given half-dollars, quarters,
> dimes, nickels, and pennies? More generally, can we write a procedure to
> compute the number of ways to
> change any given amount of money?
> This problem has a simple solution as a recursive procedure. Suppose we
> think of the types of coins
> available as arranged in some order. Then the following relation holds:
> The number of ways to change amount a using n kinds of coins equals
> the number of ways to change amount a using all but the first kind of
coin,
> plus
> the number of ways to change amount a - d using all n kinds of coins,
where
> d is the denomination
> of the first kind of coin.
> To see why this is true, observe that the ways to make change can be
divided
> into two groups: those that
> do not use any of the first kind of coin, and those that do. Therefore,
the
> total number of ways to make
> change for some amount is equal to the number of ways to make change for
the
> amount without using any
> of the first kind of coin, plus the number of ways to make change
> that we do use the first kind of
> coin. But the latter number is equal to the number of ways to make
> for the amount that remains
> after using a coin of the first kind.
> Thus, we can recursively reduce the problem of changing a given amount
> the problem of changing
> smaller amounts using fewer kinds of coins. Consider this reduction rule
> carefully, and convince yourself
> that we can use it to describe an algorithm if we specify the following
> degenerate cases:
> If a is exactly 0, we should count that as 1 way to make change.
> If a is less than 0, we should count that as 0 ways to make change.
> If n is 0, we should count that as 0 ways to make change.
> We can easily translate this description into a recursive procedure:
>
> (define (count-change amount)
> (cc amount 5))
>
> (define (cc amount kinds-of-coins)
> (cond ((= amount 0) 1)
> ((or (< amount 0) (= kinds-of-coins 0)) 0)
> (else (+ (cc amount
> (- kinds-of-coins 1))
> (cc (- amount
> (first-denomination kinds-of-coins))
> kinds-of-coins)))))
>
> (define (first-denomination kinds-of-coins)
> (cond ((= kinds-of-coins 1) 1)
> ((= kinds-of-coins 2) 5)
> ((= kinds-of-coins 3) 10)
> ((= kinds-of-coins 4) 25)
> ((= kinds-of-coins 5) 50)))
>
> (The first-denomination procedure takes as input the number of kinds of
> coins available and
> returns the denomination of the first kind. Here we are thinking of the
> coins as arranged in order from
> largest to smallest, but any order would do as well.) We can now answer
our
> original question about
> changing a dollar:
> (count-change 100)
> Count-change generates a tree-recursive process with redundancies
to
> those in our first
> implementation of fib. (It will take quite a while for that 292 to be
> computed.) On the other hand, it is
> not obvious how to design a better algorithm for computing the result,
> we leave this problem as a
> challenge. The observation that a tree-recursive process may be highly
> inefficient but often easy to specify
> and understand has led people to propose that one could get the best of
both
> worlds by designing a ``smart
> compiler'' that could transform tree-recursive procedures into more
> efficient procedures that compute the
> same result.
>
> Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je
> t'aider dans ce projet.
> En gros on part de l'idée que si f est une fonction permettant
L
> avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
> ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
>
> J'ai l'impression que la première réponse avec problème NP évoquait
> celui du plus court chemin en passant par des points obligés. Le fait
d'être
> en dimension deux change beaucoup le pb.
>
>
>
> "Himselff" a écrit dans le message de
> news:KNzhc.57140$
> > Wow merci du tuyau , je commence les recherches tout de suite , mais
ne
> > mattendais pas du tout a avoir a coder un ci gros algo ,
> >
> > youou moi qui aime les maths en plus =)
> >
> > souhaiter moi bonne chance =)
> >
> > Fred
> >
> > "Jean-Marc" wrote in message
> > news:4086c373$0$10948$
> > > "Himselff" a écrit dans le message de
> > > news:pGxhc.55193$
> > > > bonjour tout le monde,
> > > >
> > > > Je suis convaincu que le probleme est bien simple (encore une
fois ),
> > > voila
> > > > je m'explique
> > > >
> > > > Jai 2 categories de produits les rouleaux de 6 pieds et les
rouleaux
> de
> > > 12
> > > > pieds, pour realiser une commande ,
> > > >
> > > > Je dois selectionner selon le nombre de verge necessaire les
meilleurs
> > > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a
le
> > > faire
> > > > si par exemple jai assez de verge dans un rouleau , ou meme si jai
> > besoin
> > > de
> > > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je
> > > prendre
> > > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> > >
> > > Hello,
> > > ce problème n'est pas simple, il est même si compliqué que l'on ne
sait
> > pas
> > > produire une solution optimale en un temps fini. (c'est un problème
> > > complet en jargon mathématique).
> > >
> > > Ton problème est proche d'un problème générique connu sous le nom de
> > > "programme du sac à dos". Il existe des méthodes de résolution qui
> > arrivent
> > > à une solution "la plus optimale possible" en un temps fini.
> > >
> > > Tu trouveras une description de ce genre d'algorithme sur google en
> > > cherchant "knapsack problem" ou encore "programmation linéaire" ou
> encore
> > > "problème du sac à dos".
> > >
> > > Les explications et les justifications mathématiques sont un peu
(très)
> > > ardues, mais on trouve assez aisément des implémentations de
> l'algorithme,
> > > en pseudo code ou en C, aisées à traduire en VB.
> > >
> > > Jean-Marc
> > >
> > >
> >
> >
>
>
La récursivité, je ne sais pas si c'est une bonne solution, car je crois
ça ne dépile pas contrairement à une boucle, alors faut voir si on ne
pas de sortir en "fin de pile", juste une petite réflexion
Appeler une autre fonction, çan doit dépiler (end...), mais appeler sa
propre fonction, pas certain que ça dépile avant la fin du traitement...
--
Merci, @+, bye, Joe
montmartre75@iFrance.com
------------------------------------------
Avec une hache, celui qui tient le manche a toujours raison !
------------------------------------------
"Patrice Henrio" <patrice.henrio.pasdepub@laposte.net> a écrit dans le
message de news: OGFq409JEHA.1040@TK2MSFTNGP10.phx.gbl...
> J'ai traité ce genre de problème sur ce forum il y a quelques temps : il
> fallait trouver la "meilleure" façon de réaliser une somme avec
différentes
> pièces. Ici il s'agit de réaliser de la meilleure façon une longueur
> différents rouleaux de certaines longueurs chacun.
> On trouve l'explication de l'algorithme correspondant dans Structure te
> interprétation des programmes informatiques de Abelson et Sussman
> du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
> édition en anglais est disponible en ligne. [on peut télécharger son
> http://deptinfo.unice.fr/~roy/sicp.pdf)
> Il s'agit d'un algo récursif ce qui évite l'emploi de for next imbriqué
> est plus compréhensible.
> Avant de me lancer plus avant, que viennent faire les rouleaux de 6
> dans ce pb ?
> En tout cas voici ce que ça donne avec les pièces de monnaies.
> Example: Counting change
> It takes only a bit of cleverness to come up with the iterative
> algorithm. In contrast, consider the
> following problem: How many different ways can we make change of $ 1.00,
> given half-dollars, quarters,
> dimes, nickels, and pennies? More generally, can we write a procedure to
> compute the number of ways to
> change any given amount of money?
> This problem has a simple solution as a recursive procedure. Suppose we
> think of the types of coins
> available as arranged in some order. Then the following relation holds:
> The number of ways to change amount a using n kinds of coins equals
> the number of ways to change amount a using all but the first kind of
coin,
> plus
> the number of ways to change amount a - d using all n kinds of coins,
where
> d is the denomination
> of the first kind of coin.
> To see why this is true, observe that the ways to make change can be
divided
> into two groups: those that
> do not use any of the first kind of coin, and those that do. Therefore,
the
> total number of ways to make
> change for some amount is equal to the number of ways to make change for
the
> amount without using any
> of the first kind of coin, plus the number of ways to make change
> that we do use the first kind of
> coin. But the latter number is equal to the number of ways to make
> for the amount that remains
> after using a coin of the first kind.
> Thus, we can recursively reduce the problem of changing a given amount
> the problem of changing
> smaller amounts using fewer kinds of coins. Consider this reduction rule
> carefully, and convince yourself
> that we can use it to describe an algorithm if we specify the following
> degenerate cases:
> If a is exactly 0, we should count that as 1 way to make change.
> If a is less than 0, we should count that as 0 ways to make change.
> If n is 0, we should count that as 0 ways to make change.
> We can easily translate this description into a recursive procedure:
>
> (define (count-change amount)
> (cc amount 5))
>
> (define (cc amount kinds-of-coins)
> (cond ((= amount 0) 1)
> ((or (< amount 0) (= kinds-of-coins 0)) 0)
> (else (+ (cc amount
> (- kinds-of-coins 1))
> (cc (- amount
> (first-denomination kinds-of-coins))
> kinds-of-coins)))))
>
> (define (first-denomination kinds-of-coins)
> (cond ((= kinds-of-coins 1) 1)
> ((= kinds-of-coins 2) 5)
> ((= kinds-of-coins 3) 10)
> ((= kinds-of-coins 4) 25)
> ((= kinds-of-coins 5) 50)))
>
> (The first-denomination procedure takes as input the number of kinds of
> coins available and
> returns the denomination of the first kind. Here we are thinking of the
> coins as arranged in order from
> largest to smallest, but any order would do as well.) We can now answer
our
> original question about
> changing a dollar:
> (count-change 100)
> Count-change generates a tree-recursive process with redundancies
to
> those in our first
> implementation of fib. (It will take quite a while for that 292 to be
> computed.) On the other hand, it is
> not obvious how to design a better algorithm for computing the result,
> we leave this problem as a
> challenge. The observation that a tree-recursive process may be highly
> inefficient but often easy to specify
> and understand has led people to propose that one could get the best of
both
> worlds by designing a ``smart
> compiler'' that could transform tree-recursive procedures into more
> efficient procedures that compute the
> same result.
>
> Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je
> t'aider dans ce projet.
> En gros on part de l'idée que si f est une fonction permettant
L
> avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
> ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
>
> J'ai l'impression que la première réponse avec problème NP évoquait
> celui du plus court chemin en passant par des points obligés. Le fait
d'être
> en dimension deux change beaucoup le pb.
>
>
>
> "Himselff" <info@dmsinc.ca> a écrit dans le message de
> news:KNzhc.57140$Gp4.1302111@news20.bellglobal.com...
> > Wow merci du tuyau , je commence les recherches tout de suite , mais
ne
> > mattendais pas du tout a avoir a coder un ci gros algo ,
> >
> > youou moi qui aime les maths en plus =)
> >
> > souhaiter moi bonne chance =)
> >
> > Fred
> >
> > "Jean-Marc" <nospamjean_marc_n2@yahoo.fr> wrote in message
> > news:4086c373$0$10948$a0ced6e1@news.skynet.be...
> > > "Himselff" <info@dmsinc.ca> a écrit dans le message de
> > > news:pGxhc.55193$Gp4.1267131@news20.bellglobal.com...
> > > > bonjour tout le monde,
> > > >
> > > > Je suis convaincu que le probleme est bien simple (encore une
fois ),
> > > voila
> > > > je m'explique
> > > >
> > > > Jai 2 categories de produits les rouleaux de 6 pieds et les
rouleaux
> de
> > > 12
> > > > pieds, pour realiser une commande ,
> > > >
> > > > Je dois selectionner selon le nombre de verge necessaire les
meilleurs
> > > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a
le
> > > faire
> > > > si par exemple jai assez de verge dans un rouleau , ou meme si jai
> > besoin
> > > de
> > > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je
> > > prendre
> > > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> > >
> > > Hello,
> > > ce problème n'est pas simple, il est même si compliqué que l'on ne
sait
> > pas
> > > produire une solution optimale en un temps fini. (c'est un problème
> > > complet en jargon mathématique).
> > >
> > > Ton problème est proche d'un problème générique connu sous le nom de
> > > "programme du sac à dos". Il existe des méthodes de résolution qui
> > arrivent
> > > à une solution "la plus optimale possible" en un temps fini.
> > >
> > > Tu trouveras une description de ce genre d'algorithme sur google en
> > > cherchant "knapsack problem" ou encore "programmation linéaire" ou
> encore
> > > "problème du sac à dos".
> > >
> > > Les explications et les justifications mathématiques sont un peu
(très)
> > > ardues, mais on trouve assez aisément des implémentations de
> l'algorithme,
> > > en pseudo code ou en C, aisées à traduire en VB.
> > >
> > > Jean-Marc
> > >
> > >
> >
> >
>
>
La récursivité, je ne sais pas si c'est une bonne solution, car je crois
ça ne dépile pas contrairement à une boucle, alors faut voir si on ne
pas de sortir en "fin de pile", juste une petite réflexion
Appeler une autre fonction, çan doit dépiler (end...), mais appeler sa
propre fonction, pas certain que ça dépile avant la fin du traitement...
--
Merci, @+, bye, Joe
------------------------------------------
Avec une hache, celui qui tient le manche a toujours raison !
------------------------------------------
"Patrice Henrio" a écrit dans le
message de news:
> J'ai traité ce genre de problème sur ce forum il y a quelques temps : il
> fallait trouver la "meilleure" façon de réaliser une somme avec
différentes
> pièces. Ici il s'agit de réaliser de la meilleure façon une longueur
> différents rouleaux de certaines longueurs chacun.
> On trouve l'explication de l'algorithme correspondant dans Structure te
> interprétation des programmes informatiques de Abelson et Sussman
> du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
> édition en anglais est disponible en ligne. [on peut télécharger son
> http://deptinfo.unice.fr/~roy/sicp.pdf)
> Il s'agit d'un algo récursif ce qui évite l'emploi de for next imbriqué
> est plus compréhensible.
> Avant de me lancer plus avant, que viennent faire les rouleaux de 6
> dans ce pb ?
> En tout cas voici ce que ça donne avec les pièces de monnaies.
> Example: Counting change
> It takes only a bit of cleverness to come up with the iterative
> algorithm. In contrast, consider the
> following problem: How many different ways can we make change of $ 1.00,
> given half-dollars, quarters,
> dimes, nickels, and pennies? More generally, can we write a procedure to
> compute the number of ways to
> change any given amount of money?
> This problem has a simple solution as a recursive procedure. Suppose we
> think of the types of coins
> available as arranged in some order. Then the following relation holds:
> The number of ways to change amount a using n kinds of coins equals
> the number of ways to change amount a using all but the first kind of
coin,
> plus
> the number of ways to change amount a - d using all n kinds of coins,
where
> d is the denomination
> of the first kind of coin.
> To see why this is true, observe that the ways to make change can be
divided
> into two groups: those that
> do not use any of the first kind of coin, and those that do. Therefore,
the
> total number of ways to make
> change for some amount is equal to the number of ways to make change for
the
> amount without using any
> of the first kind of coin, plus the number of ways to make change
> that we do use the first kind of
> coin. But the latter number is equal to the number of ways to make
> for the amount that remains
> after using a coin of the first kind.
> Thus, we can recursively reduce the problem of changing a given amount
> the problem of changing
> smaller amounts using fewer kinds of coins. Consider this reduction rule
> carefully, and convince yourself
> that we can use it to describe an algorithm if we specify the following
> degenerate cases:
> If a is exactly 0, we should count that as 1 way to make change.
> If a is less than 0, we should count that as 0 ways to make change.
> If n is 0, we should count that as 0 ways to make change.
> We can easily translate this description into a recursive procedure:
>
> (define (count-change amount)
> (cc amount 5))
>
> (define (cc amount kinds-of-coins)
> (cond ((= amount 0) 1)
> ((or (< amount 0) (= kinds-of-coins 0)) 0)
> (else (+ (cc amount
> (- kinds-of-coins 1))
> (cc (- amount
> (first-denomination kinds-of-coins))
> kinds-of-coins)))))
>
> (define (first-denomination kinds-of-coins)
> (cond ((= kinds-of-coins 1) 1)
> ((= kinds-of-coins 2) 5)
> ((= kinds-of-coins 3) 10)
> ((= kinds-of-coins 4) 25)
> ((= kinds-of-coins 5) 50)))
>
> (The first-denomination procedure takes as input the number of kinds of
> coins available and
> returns the denomination of the first kind. Here we are thinking of the
> coins as arranged in order from
> largest to smallest, but any order would do as well.) We can now answer
our
> original question about
> changing a dollar:
> (count-change 100)
> Count-change generates a tree-recursive process with redundancies
to
> those in our first
> implementation of fib. (It will take quite a while for that 292 to be
> computed.) On the other hand, it is
> not obvious how to design a better algorithm for computing the result,
> we leave this problem as a
> challenge. The observation that a tree-recursive process may be highly
> inefficient but often easy to specify
> and understand has led people to propose that one could get the best of
both
> worlds by designing a ``smart
> compiler'' that could transform tree-recursive procedures into more
> efficient procedures that compute the
> same result.
>
> Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je
> t'aider dans ce projet.
> En gros on part de l'idée que si f est une fonction permettant
L
> avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
> ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
>
> J'ai l'impression que la première réponse avec problème NP évoquait
> celui du plus court chemin en passant par des points obligés. Le fait
d'être
> en dimension deux change beaucoup le pb.
>
>
>
> "Himselff" a écrit dans le message de
> news:KNzhc.57140$
> > Wow merci du tuyau , je commence les recherches tout de suite , mais
ne
> > mattendais pas du tout a avoir a coder un ci gros algo ,
> >
> > youou moi qui aime les maths en plus =)
> >
> > souhaiter moi bonne chance =)
> >
> > Fred
> >
> > "Jean-Marc" wrote in message
> > news:4086c373$0$10948$
> > > "Himselff" a écrit dans le message de
> > > news:pGxhc.55193$
> > > > bonjour tout le monde,
> > > >
> > > > Je suis convaincu que le probleme est bien simple (encore une
fois ),
> > > voila
> > > > je m'explique
> > > >
> > > > Jai 2 categories de produits les rouleaux de 6 pieds et les
rouleaux
> de
> > > 12
> > > > pieds, pour realiser une commande ,
> > > >
> > > > Je dois selectionner selon le nombre de verge necessaire les
meilleurs
> > > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien a
le
> > > faire
> > > > si par exemple jai assez de verge dans un rouleau , ou meme si jai
> > besoin
> > > de
> > > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je
> > > prendre
> > > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> > >
> > > Hello,
> > > ce problème n'est pas simple, il est même si compliqué que l'on ne
sait
> > pas
> > > produire une solution optimale en un temps fini. (c'est un problème
> > > complet en jargon mathématique).
> > >
> > > Ton problème est proche d'un problème générique connu sous le nom de
> > > "programme du sac à dos". Il existe des méthodes de résolution qui
> > arrivent
> > > à une solution "la plus optimale possible" en un temps fini.
> > >
> > > Tu trouveras une description de ce genre d'algorithme sur google en
> > > cherchant "knapsack problem" ou encore "programmation linéaire" ou
> encore
> > > "problème du sac à dos".
> > >
> > > Les explications et les justifications mathématiques sont un peu
(très)
> > > ardues, mais on trouve assez aisément des implémentations de
> l'algorithme,
> > > en pseudo code ou en C, aisées à traduire en VB.
> > >
> > > Jean-Marc
> > >
> > >
> >
> >
>
>
Bonjour ,
J'ai pris le temps de lire toute la documentation sur le probleme, je
comprend tres bien le probleme et la solution, mais pour ce qui est de
mettre tout sa en pratique cest une autre histoire,
ce que je crois, cest que premiere des choses je devrais mettre tout les
rouleaux dans une variable tableau en ordre croissant qui nous permeterais
detre capable de trier plus aisement par la suite, ensuite et bien inserer
lalgorythme qui va trouver le - les meilleurs rouleau !
Jattend vos suggestions car je ne sais trop de quelle facon debuter !
Merci
Fred
"le_troll" wrote in message
news:#
> La récursivité, je ne sais pas si c'est une bonne solution, car je crois
que
> ça ne dépile pas contrairement à une boucle, alors faut voir si on ne
risque
> pas de sortir en "fin de pile", juste une petite réflexion
supplémentaire...
> Appeler une autre fonction, çan doit dépiler (end...), mais appeler sa
> propre fonction, pas certain que ça dépile avant la fin du traitement...
> --
> Merci, @+, bye, Joe
>
> ------------------------------------------
> Avec une hache, celui qui tient le manche a toujours raison !
> ------------------------------------------
>
>
> "Patrice Henrio" a écrit dans le
> message de news:
> > J'ai traité ce genre de problème sur ce forum il y a quelques temps :
> > fallait trouver la "meilleure" façon de réaliser une somme avec
> différentes
> > pièces. Ici il s'agit de réaliser de la meilleure façon une longueur
avec
> > différents rouleaux de certaines longueurs chacun.
> > On trouve l'explication de l'algorithme correspondant dans Structure
> > interprétation des programmes informatiques de Abelson et Sussman
(exemple
> > du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
> > édition en anglais est disponible en ligne. [on peut télécharger son
pdf],
> > http://deptinfo.unice.fr/~roy/sicp.pdf)
> > Il s'agit d'un algo récursif ce qui évite l'emploi de for next
et
> > est plus compréhensible.
> > Avant de me lancer plus avant, que viennent faire les rouleaux de 6
pieds
> > dans ce pb ?
> > En tout cas voici ce que ça donne avec les pièces de monnaies.
> > Example: Counting change
> > It takes only a bit of cleverness to come up with the iterative
Fibonacci
> > algorithm. In contrast, consider the
> > following problem: How many different ways can we make change of $
> > given half-dollars, quarters,
> > dimes, nickels, and pennies? More generally, can we write a procedure
> > compute the number of ways to
> > change any given amount of money?
> > This problem has a simple solution as a recursive procedure. Suppose
> > think of the types of coins
> > available as arranged in some order. Then the following relation
> > The number of ways to change amount a using n kinds of coins equals
> > the number of ways to change amount a using all but the first kind of
> coin,
> > plus
> > the number of ways to change amount a - d using all n kinds of coins,
> where
> > d is the denomination
> > of the first kind of coin.
> > To see why this is true, observe that the ways to make change can be
> divided
> > into two groups: those that
> > do not use any of the first kind of coin, and those that do.
> the
> > total number of ways to make
> > change for some amount is equal to the number of ways to make change
> the
> > amount without using any
> > of the first kind of coin, plus the number of ways to make change
assuming
> > that we do use the first kind of
> > coin. But the latter number is equal to the number of ways to make
change
> > for the amount that remains
> > after using a coin of the first kind.
> > Thus, we can recursively reduce the problem of changing a given amount
to
> > the problem of changing
> > smaller amounts using fewer kinds of coins. Consider this reduction
> > carefully, and convince yourself
> > that we can use it to describe an algorithm if we specify the
> > degenerate cases:
> > If a is exactly 0, we should count that as 1 way to make change.
> > If a is less than 0, we should count that as 0 ways to make change.
> > If n is 0, we should count that as 0 ways to make change.
> > We can easily translate this description into a recursive procedure:
> >
> > (define (count-change amount)
> > (cc amount 5))
> >
> > (define (cc amount kinds-of-coins)
> > (cond ((= amount 0) 1)
> > ((or (< amount 0) (= kinds-of-coins 0)) 0)
> > (else (+ (cc amount
> > (- kinds-of-coins 1))
> > (cc (- amount
> > (first-denomination kinds-of-coins))
> > kinds-of-coins)))))
> >
> > (define (first-denomination kinds-of-coins)
> > (cond ((= kinds-of-coins 1) 1)
> > ((= kinds-of-coins 2) 5)
> > ((= kinds-of-coins 3) 10)
> > ((= kinds-of-coins 4) 25)
> > ((= kinds-of-coins 5) 50)))
> >
> > (The first-denomination procedure takes as input the number of kinds
> > coins available and
> > returns the denomination of the first kind. Here we are thinking of
> > coins as arranged in order from
> > largest to smallest, but any order would do as well.) We can now
> our
> > original question about
> > changing a dollar:
> > (count-change 100)
> > Count-change generates a tree-recursive process with redundancies
similar
> to
> > those in our first
> > implementation of fib. (It will take quite a while for that 292 to be
> > computed.) On the other hand, it is
> > not obvious how to design a better algorithm for computing the result,
and
> > we leave this problem as a
> > challenge. The observation that a tree-recursive process may be highly
> > inefficient but often easy to specify
> > and understand has led people to propose that one could get the best
> both
> > worlds by designing a ``smart
> > compiler'' that could transform tree-recursive procedures into more
> > efficient procedures that compute the
> > same result.
> >
> > Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je
peux
> > t'aider dans ce projet.
> > En gros on part de l'idée que si f est une fonction permettant
d'atteindre
> L
> > avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
> > ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
> >
> > J'ai l'impression que la première réponse avec problème NP évoquait
plutôt
> > celui du plus court chemin en passant par des points obligés. Le fait
> d'être
> > en dimension deux change beaucoup le pb.
> >
> >
> >
> > "Himselff" a écrit dans le message de
> > news:KNzhc.57140$
> > > Wow merci du tuyau , je commence les recherches tout de suite , mais
je
> ne
> > > mattendais pas du tout a avoir a coder un ci gros algo ,
> > >
> > > youou moi qui aime les maths en plus =)
> > >
> > > souhaiter moi bonne chance =)
> > >
> > > Fred
> > >
> > > "Jean-Marc" wrote in message
> > > news:4086c373$0$10948$
> > > > "Himselff" a écrit dans le message de
> > > > news:pGxhc.55193$
> > > > > bonjour tout le monde,
> > > > >
> > > > > Je suis convaincu que le probleme est bien simple (encore une
> fois ),
> > > > voila
> > > > > je m'explique
> > > > >
> > > > > Jai 2 categories de produits les rouleaux de 6 pieds et les
> rouleaux
> > de
> > > > 12
> > > > > pieds, pour realiser une commande ,
> > > > >
> > > > > Je dois selectionner selon le nombre de verge necessaire les
> meilleurs
> > > > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien
> le
> > > > faire
> > > > > si par exemple jai assez de verge dans un rouleau , ou meme si
> > > besoin
> > > > de
> > > > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je
dois
> > > > prendre
> > > > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> > > >
> > > > Hello,
> > > > ce problème n'est pas simple, il est même si compliqué que l'on ne
> sait
> > > pas
> > > > produire une solution optimale en un temps fini. (c'est un
NP
> > > > complet en jargon mathématique).
> > > >
> > > > Ton problème est proche d'un problème générique connu sous le nom
> > > > "programme du sac à dos". Il existe des méthodes de résolution qui
> > > arrivent
> > > > à une solution "la plus optimale possible" en un temps fini.
> > > >
> > > > Tu trouveras une description de ce genre d'algorithme sur google
> > > > cherchant "knapsack problem" ou encore "programmation linéaire" ou
> > encore
> > > > "problème du sac à dos".
> > > >
> > > > Les explications et les justifications mathématiques sont un peu
> (très)
> > > > ardues, mais on trouve assez aisément des implémentations de
> > l'algorithme,
> > > > en pseudo code ou en C, aisées à traduire en VB.
> > > >
> > > > Jean-Marc
> > > >
> > > >
> > >
> > >
> >
> >
>
>
Bonjour ,
J'ai pris le temps de lire toute la documentation sur le probleme, je
comprend tres bien le probleme et la solution, mais pour ce qui est de
mettre tout sa en pratique cest une autre histoire,
ce que je crois, cest que premiere des choses je devrais mettre tout les
rouleaux dans une variable tableau en ordre croissant qui nous permeterais
detre capable de trier plus aisement par la suite, ensuite et bien inserer
lalgorythme qui va trouver le - les meilleurs rouleau !
Jattend vos suggestions car je ne sais trop de quelle facon debuter !
Merci
Fred
"le_troll" <le_trol@paris.fr> wrote in message
news:#Cl7aWFKEHA.2012@TK2MSFTNGP11.phx.gbl...
> La récursivité, je ne sais pas si c'est une bonne solution, car je crois
que
> ça ne dépile pas contrairement à une boucle, alors faut voir si on ne
risque
> pas de sortir en "fin de pile", juste une petite réflexion
supplémentaire...
> Appeler une autre fonction, çan doit dépiler (end...), mais appeler sa
> propre fonction, pas certain que ça dépile avant la fin du traitement...
> --
> Merci, @+, bye, Joe
> montmartre75@iFrance.com
> ------------------------------------------
> Avec une hache, celui qui tient le manche a toujours raison !
> ------------------------------------------
>
>
> "Patrice Henrio" <patrice.henrio.pasdepub@laposte.net> a écrit dans le
> message de news: OGFq409JEHA.1040@TK2MSFTNGP10.phx.gbl...
> > J'ai traité ce genre de problème sur ce forum il y a quelques temps :
> > fallait trouver la "meilleure" façon de réaliser une somme avec
> différentes
> > pièces. Ici il s'agit de réaliser de la meilleure façon une longueur
avec
> > différents rouleaux de certaines longueurs chacun.
> > On trouve l'explication de l'algorithme correspondant dans Structure
> > interprétation des programmes informatiques de Abelson et Sussman
(exemple
> > du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
> > édition en anglais est disponible en ligne. [on peut télécharger son
pdf],
> > http://deptinfo.unice.fr/~roy/sicp.pdf)
> > Il s'agit d'un algo récursif ce qui évite l'emploi de for next
et
> > est plus compréhensible.
> > Avant de me lancer plus avant, que viennent faire les rouleaux de 6
pieds
> > dans ce pb ?
> > En tout cas voici ce que ça donne avec les pièces de monnaies.
> > Example: Counting change
> > It takes only a bit of cleverness to come up with the iterative
Fibonacci
> > algorithm. In contrast, consider the
> > following problem: How many different ways can we make change of $
> > given half-dollars, quarters,
> > dimes, nickels, and pennies? More generally, can we write a procedure
> > compute the number of ways to
> > change any given amount of money?
> > This problem has a simple solution as a recursive procedure. Suppose
> > think of the types of coins
> > available as arranged in some order. Then the following relation
> > The number of ways to change amount a using n kinds of coins equals
> > the number of ways to change amount a using all but the first kind of
> coin,
> > plus
> > the number of ways to change amount a - d using all n kinds of coins,
> where
> > d is the denomination
> > of the first kind of coin.
> > To see why this is true, observe that the ways to make change can be
> divided
> > into two groups: those that
> > do not use any of the first kind of coin, and those that do.
> the
> > total number of ways to make
> > change for some amount is equal to the number of ways to make change
> the
> > amount without using any
> > of the first kind of coin, plus the number of ways to make change
assuming
> > that we do use the first kind of
> > coin. But the latter number is equal to the number of ways to make
change
> > for the amount that remains
> > after using a coin of the first kind.
> > Thus, we can recursively reduce the problem of changing a given amount
to
> > the problem of changing
> > smaller amounts using fewer kinds of coins. Consider this reduction
> > carefully, and convince yourself
> > that we can use it to describe an algorithm if we specify the
> > degenerate cases:
> > If a is exactly 0, we should count that as 1 way to make change.
> > If a is less than 0, we should count that as 0 ways to make change.
> > If n is 0, we should count that as 0 ways to make change.
> > We can easily translate this description into a recursive procedure:
> >
> > (define (count-change amount)
> > (cc amount 5))
> >
> > (define (cc amount kinds-of-coins)
> > (cond ((= amount 0) 1)
> > ((or (< amount 0) (= kinds-of-coins 0)) 0)
> > (else (+ (cc amount
> > (- kinds-of-coins 1))
> > (cc (- amount
> > (first-denomination kinds-of-coins))
> > kinds-of-coins)))))
> >
> > (define (first-denomination kinds-of-coins)
> > (cond ((= kinds-of-coins 1) 1)
> > ((= kinds-of-coins 2) 5)
> > ((= kinds-of-coins 3) 10)
> > ((= kinds-of-coins 4) 25)
> > ((= kinds-of-coins 5) 50)))
> >
> > (The first-denomination procedure takes as input the number of kinds
> > coins available and
> > returns the denomination of the first kind. Here we are thinking of
> > coins as arranged in order from
> > largest to smallest, but any order would do as well.) We can now
> our
> > original question about
> > changing a dollar:
> > (count-change 100)
> > Count-change generates a tree-recursive process with redundancies
similar
> to
> > those in our first
> > implementation of fib. (It will take quite a while for that 292 to be
> > computed.) On the other hand, it is
> > not obvious how to design a better algorithm for computing the result,
and
> > we leave this problem as a
> > challenge. The observation that a tree-recursive process may be highly
> > inefficient but often easy to specify
> > and understand has led people to propose that one could get the best
> both
> > worlds by designing a ``smart
> > compiler'' that could transform tree-recursive procedures into more
> > efficient procedures that compute the
> > same result.
> >
> > Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je
peux
> > t'aider dans ce projet.
> > En gros on part de l'idée que si f est une fonction permettant
d'atteindre
> L
> > avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
> > ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
> >
> > J'ai l'impression que la première réponse avec problème NP évoquait
plutôt
> > celui du plus court chemin en passant par des points obligés. Le fait
> d'être
> > en dimension deux change beaucoup le pb.
> >
> >
> >
> > "Himselff" <info@dmsinc.ca> a écrit dans le message de
> > news:KNzhc.57140$Gp4.1302111@news20.bellglobal.com...
> > > Wow merci du tuyau , je commence les recherches tout de suite , mais
je
> ne
> > > mattendais pas du tout a avoir a coder un ci gros algo ,
> > >
> > > youou moi qui aime les maths en plus =)
> > >
> > > souhaiter moi bonne chance =)
> > >
> > > Fred
> > >
> > > "Jean-Marc" <nospamjean_marc_n2@yahoo.fr> wrote in message
> > > news:4086c373$0$10948$a0ced6e1@news.skynet.be...
> > > > "Himselff" <info@dmsinc.ca> a écrit dans le message de
> > > > news:pGxhc.55193$Gp4.1267131@news20.bellglobal.com...
> > > > > bonjour tout le monde,
> > > > >
> > > > > Je suis convaincu que le probleme est bien simple (encore une
> fois ),
> > > > voila
> > > > > je m'explique
> > > > >
> > > > > Jai 2 categories de produits les rouleaux de 6 pieds et les
> rouleaux
> > de
> > > > 12
> > > > > pieds, pour realiser une commande ,
> > > > >
> > > > > Je dois selectionner selon le nombre de verge necessaire les
> meilleurs
> > > > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien
> le
> > > > faire
> > > > > si par exemple jai assez de verge dans un rouleau , ou meme si
> > > besoin
> > > > de
> > > > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je
dois
> > > > prendre
> > > > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> > > >
> > > > Hello,
> > > > ce problème n'est pas simple, il est même si compliqué que l'on ne
> sait
> > > pas
> > > > produire une solution optimale en un temps fini. (c'est un
NP
> > > > complet en jargon mathématique).
> > > >
> > > > Ton problème est proche d'un problème générique connu sous le nom
> > > > "programme du sac à dos". Il existe des méthodes de résolution qui
> > > arrivent
> > > > à une solution "la plus optimale possible" en un temps fini.
> > > >
> > > > Tu trouveras une description de ce genre d'algorithme sur google
> > > > cherchant "knapsack problem" ou encore "programmation linéaire" ou
> > encore
> > > > "problème du sac à dos".
> > > >
> > > > Les explications et les justifications mathématiques sont un peu
> (très)
> > > > ardues, mais on trouve assez aisément des implémentations de
> > l'algorithme,
> > > > en pseudo code ou en C, aisées à traduire en VB.
> > > >
> > > > Jean-Marc
> > > >
> > > >
> > >
> > >
> >
> >
>
>
Bonjour ,
J'ai pris le temps de lire toute la documentation sur le probleme, je
comprend tres bien le probleme et la solution, mais pour ce qui est de
mettre tout sa en pratique cest une autre histoire,
ce que je crois, cest que premiere des choses je devrais mettre tout les
rouleaux dans une variable tableau en ordre croissant qui nous permeterais
detre capable de trier plus aisement par la suite, ensuite et bien inserer
lalgorythme qui va trouver le - les meilleurs rouleau !
Jattend vos suggestions car je ne sais trop de quelle facon debuter !
Merci
Fred
"le_troll" wrote in message
news:#
> La récursivité, je ne sais pas si c'est une bonne solution, car je crois
que
> ça ne dépile pas contrairement à une boucle, alors faut voir si on ne
risque
> pas de sortir en "fin de pile", juste une petite réflexion
supplémentaire...
> Appeler une autre fonction, çan doit dépiler (end...), mais appeler sa
> propre fonction, pas certain que ça dépile avant la fin du traitement...
> --
> Merci, @+, bye, Joe
>
> ------------------------------------------
> Avec une hache, celui qui tient le manche a toujours raison !
> ------------------------------------------
>
>
> "Patrice Henrio" a écrit dans le
> message de news:
> > J'ai traité ce genre de problème sur ce forum il y a quelques temps :
> > fallait trouver la "meilleure" façon de réaliser une somme avec
> différentes
> > pièces. Ici il s'agit de réaliser de la meilleure façon une longueur
avec
> > différents rouleaux de certaines longueurs chacun.
> > On trouve l'explication de l'algorithme correspondant dans Structure
> > interprétation des programmes informatiques de Abelson et Sussman
(exemple
> > du chapitre 1.2.2). (la 1ère édition en français est épuisée. La 2ème
> > édition en anglais est disponible en ligne. [on peut télécharger son
pdf],
> > http://deptinfo.unice.fr/~roy/sicp.pdf)
> > Il s'agit d'un algo récursif ce qui évite l'emploi de for next
et
> > est plus compréhensible.
> > Avant de me lancer plus avant, que viennent faire les rouleaux de 6
pieds
> > dans ce pb ?
> > En tout cas voici ce que ça donne avec les pièces de monnaies.
> > Example: Counting change
> > It takes only a bit of cleverness to come up with the iterative
Fibonacci
> > algorithm. In contrast, consider the
> > following problem: How many different ways can we make change of $
> > given half-dollars, quarters,
> > dimes, nickels, and pennies? More generally, can we write a procedure
> > compute the number of ways to
> > change any given amount of money?
> > This problem has a simple solution as a recursive procedure. Suppose
> > think of the types of coins
> > available as arranged in some order. Then the following relation
> > The number of ways to change amount a using n kinds of coins equals
> > the number of ways to change amount a using all but the first kind of
> coin,
> > plus
> > the number of ways to change amount a - d using all n kinds of coins,
> where
> > d is the denomination
> > of the first kind of coin.
> > To see why this is true, observe that the ways to make change can be
> divided
> > into two groups: those that
> > do not use any of the first kind of coin, and those that do.
> the
> > total number of ways to make
> > change for some amount is equal to the number of ways to make change
> the
> > amount without using any
> > of the first kind of coin, plus the number of ways to make change
assuming
> > that we do use the first kind of
> > coin. But the latter number is equal to the number of ways to make
change
> > for the amount that remains
> > after using a coin of the first kind.
> > Thus, we can recursively reduce the problem of changing a given amount
to
> > the problem of changing
> > smaller amounts using fewer kinds of coins. Consider this reduction
> > carefully, and convince yourself
> > that we can use it to describe an algorithm if we specify the
> > degenerate cases:
> > If a is exactly 0, we should count that as 1 way to make change.
> > If a is less than 0, we should count that as 0 ways to make change.
> > If n is 0, we should count that as 0 ways to make change.
> > We can easily translate this description into a recursive procedure:
> >
> > (define (count-change amount)
> > (cc amount 5))
> >
> > (define (cc amount kinds-of-coins)
> > (cond ((= amount 0) 1)
> > ((or (< amount 0) (= kinds-of-coins 0)) 0)
> > (else (+ (cc amount
> > (- kinds-of-coins 1))
> > (cc (- amount
> > (first-denomination kinds-of-coins))
> > kinds-of-coins)))))
> >
> > (define (first-denomination kinds-of-coins)
> > (cond ((= kinds-of-coins 1) 1)
> > ((= kinds-of-coins 2) 5)
> > ((= kinds-of-coins 3) 10)
> > ((= kinds-of-coins 4) 25)
> > ((= kinds-of-coins 5) 50)))
> >
> > (The first-denomination procedure takes as input the number of kinds
> > coins available and
> > returns the denomination of the first kind. Here we are thinking of
> > coins as arranged in order from
> > largest to smallest, but any order would do as well.) We can now
> our
> > original question about
> > changing a dollar:
> > (count-change 100)
> > Count-change generates a tree-recursive process with redundancies
similar
> to
> > those in our first
> > implementation of fib. (It will take quite a while for that 292 to be
> > computed.) On the other hand, it is
> > not obvious how to design a better algorithm for computing the result,
and
> > we leave this problem as a
> > challenge. The observation that a tree-recursive process may be highly
> > inefficient but often easy to specify
> > and understand has led people to propose that one could get the best
> both
> > worlds by designing a ``smart
> > compiler'' that could transform tree-recursive procedures into more
> > efficient procedures that compute the
> > same result.
> >
> > Si tu n'es pas familiarisé avec le Lisp et les langages récursifs, je
peux
> > t'aider dans ce projet.
> > En gros on part de l'idée que si f est une fonction permettant
d'atteindre
> L
> > avec des rouleaux d'un ensemble R, alors f atteint L-r1 avec le même
> > ensemble R, dans lequel r1 est la longueur du premier rouleau utilisé.
> >
> > J'ai l'impression que la première réponse avec problème NP évoquait
plutôt
> > celui du plus court chemin en passant par des points obligés. Le fait
> d'être
> > en dimension deux change beaucoup le pb.
> >
> >
> >
> > "Himselff" a écrit dans le message de
> > news:KNzhc.57140$
> > > Wow merci du tuyau , je commence les recherches tout de suite , mais
je
> ne
> > > mattendais pas du tout a avoir a coder un ci gros algo ,
> > >
> > > youou moi qui aime les maths en plus =)
> > >
> > > souhaiter moi bonne chance =)
> > >
> > > Fred
> > >
> > > "Jean-Marc" wrote in message
> > > news:4086c373$0$10948$
> > > > "Himselff" a écrit dans le message de
> > > > news:pGxhc.55193$
> > > > > bonjour tout le monde,
> > > > >
> > > > > Je suis convaincu que le probleme est bien simple (encore une
> fois ),
> > > > voila
> > > > > je m'explique
> > > > >
> > > > > Jai 2 categories de produits les rouleaux de 6 pieds et les
> rouleaux
> > de
> > > > 12
> > > > > pieds, pour realiser une commande ,
> > > > >
> > > > > Je dois selectionner selon le nombre de verge necessaire les
> meilleurs
> > > > > rouleaux pour avoir le moin de perte possible, Jarrive tres bien
> le
> > > > faire
> > > > > si par exemple jai assez de verge dans un rouleau , ou meme si
> > > besoin
> > > > de
> > > > > tout les 6 pieds et un seul 12 pieds (par ordre de priorite je
dois
> > > > prendre
> > > > > tout les 6 pieds avant de songer a prendre les 12 pieds)
> > > >
> > > > Hello,
> > > > ce problème n'est pas simple, il est même si compliqué que l'on ne
> sait
> > > pas
> > > > produire une solution optimale en un temps fini. (c'est un
NP
> > > > complet en jargon mathématique).
> > > >
> > > > Ton problème est proche d'un problème générique connu sous le nom
> > > > "programme du sac à dos". Il existe des méthodes de résolution qui
> > > arrivent
> > > > à une solution "la plus optimale possible" en un temps fini.
> > > >
> > > > Tu trouveras une description de ce genre d'algorithme sur google
> > > > cherchant "knapsack problem" ou encore "programmation linéaire" ou
> > encore
> > > > "problème du sac à dos".
> > > >
> > > > Les explications et les justifications mathématiques sont un peu
> (très)
> > > > ardues, mais on trouve assez aisément des implémentations de
> > l'algorithme,
> > > > en pseudo code ou en C, aisées à traduire en VB.
> > > >
> > > > Jean-Marc
> > > >
> > > >
> > >
> > >
> >
> >
>
>