Variation de knapsack

[fatal_error]

bj,

j'ai n items, resp i1,...,i_n.
chaque item a une valeur de vente: x_1,...,x_n, comprise entre 1 et 20 (inclus)

lorsque je vends des items pour une somme totale s, je marque E(s/40) points. (E partie entière)
ex:
si s=40, je marque un point.
si s=79, je marque qu'un seul point aussi.
en revanche (évidemment) si je vends pour 80, je marque deux points

quels sont les items à vendre, tels que je marque un max de points, mais j'ai le moins de "gachis".
idem il vaut mieux vendre des items pour une somme de 80 plutot que d'autre dont la somme vaut 81.

edit: j'ai une solution, mais curieux de savoir comment vous aborderiez le pb

[LeJeu]

Bonjour Fatal,

Si je t'ai suivi : le gain maximum est celui obtenu en vendant " tout"
G = E(x1 +......+ xn)/40)

si S= x1+... xn est un multiple de 40 , on remballe le stand , on a zéro gâchis

Sinon on va retirer des Xi pour diminuer la somme tout en étant >= au multiple de 40 inférieur à S que nous appellerons S0 , donc en conservant un gain de G

Comme je suis sans ordi , je vais faire simple, gloutonnement mais à la main , je trie les Xi dans l'ordre croissant , et en partant du plus grand si je peux le retirer à S ( sans être inférieur à S0)je le retire et je continue
Ce n'est pas l'optimum mais ca peut être une bonne approximation !

Je sais, je n'ai pas utilise l’hypothèse xi<20, et surtout ma solution est plutôt simpliste,j'ai du zapper une complication quelque part!

[lyceen95]

Soit S = la somme des
Si S est un multiple de 40, c'est simple, on vend tout, on aura un nombre de points maximum, et aucun gachis.
Si S n'est pas un multiple , soit G = S mod 40 (= le reste de la division entière de S par 40) , et P = S-G ( le plus grand multiple de 40 inférieur ou égal à S)

On va essayer d'empocher nos P/40 points, c'est le maximum de points qu'on peut encaisser, mais en faisant le moins de gachis possible.
Donc si on arrive à combiner quelques articles dont le montant donne G, on va vendre tous les articles sauf ceux là, on aura nos P/40 points, sans aucun gachis.
Ce qu'on cherche, c'est donc une combinaison de x éléments (x= 0, 1 , ou plus), qui donne un montant aussi proche que possible de G, mais inférieur ou égal à G.
Le traitement pour faire cette recherche ne devrait pas être très long, ni très compliqué.

[fatal_error]

@leJeu
bon retour déjà et oui c'est la solution probablement la plus pragmatique (celle que je fais quand je joue par flemme de quitter le jeu )

@lyceen95
je suis parvenu au même raisonnement, comme le titre de ce fil l'indique, la dernière recherche se résoud simplement via knapsack (maxer la distance à G (par inférieur) revient à dire que chaque item a un poids égal à sa valeur, et donc à maxer la somme, sous contrainte de poids inférieure ou égale à G)