Algorithme de prix des remises en vrac

Question

Je conçois un site d'enchères chinois.

Les billets (5 $, 1012 $ & 20 $) sont vendus soit individuellement, soit par paquets pour obtenir des rabais. Il existe plusieurs forfaits de billets par exemple:

1. 5- 5 $ Billets = reçoivent 10%
2. 5 billets à 10 $ = reçoivent 10%
3. 5- 20 $ Billets = reçoivent 10%
4. 5- 5 $ + billets de 5 à 10 $ billets + 5- 20 $ billets = reçoivent 15%

Lorsque les utilisateurs ajoutent des billets à leur panier, je dois comprendre pour leur donner le paquet le moins cher (s). l'astuce est que si un utilisateur ajoute 4 tickets à 5 $ + 5 billets à 10 tickets + 5 tickets à 20 $, il devrait tout de même lui donner le package # 4 puisque ce serait le moins cher pour lui.

Toute aide pour trouver un algorithme pour résoudre ce problème, ou des conseils serait grandement apprécier.

grâce

EDIT

je me suis dit la réponse, merci tous, mais le code est long.

Je posterai le code de réponse si quelqu'un est toujours intéressé.

Answer 1

Une approche est la programmation dynamique. L'idée est que si l'acheteur veut x de l'élément A, y de l'élément B, et z de l'élément C, alors vous devez calculer pour tous les triplets (x ', y', z ') avec 0 < = x '< = x et 0 < = y' = y < et 0 < = z '= z < le meilleur moyen pour obtenir au moins x' de A, y 'de B, et z' de C. pseudocode:

for x' = 0 to x 
    for y' = 0 to y 
     for z' = 0 to z 
      cheapest[(x', y', z')] = min over all packages p of (price(p) + cheapest[residual demand after buying p]) 
      next_package[(x', y', z')] = the best package p 

Ensuite, vous pouvez travailler en arrière à partir de (x, y, z) en ajoutant au panier les paquets indiqués par next_package.

S'il existe de nombreux types d'articles différents ou s'il y en a beaucoup, les branchements et les reliures peuvent constituer un meilleur choix.

Answer 2

D'abord, calculez le nombre de packages 4 complets dont vous avez besoin. Faites-les sortir du chemin.

full_package_4_count = min(x, y, z) mod 5. 

x = x - 5 * full_package_4_count 
y = y - 5 * full_package_4_count 
z = z - 5 * full_package_4_count 

Maintenant, il peut y avoir encore la peine d'acheter un peu plus 4s de l'emballage, même si elles ne voulaient pas vraiment acheter que beaucoup de billets.

Combien d'entre elles pourraient être?

partial_package_4_max = (max(x, y, z) + 4) mod 5 

boucle maintenant pour essayer chacun de ces out:

best_price = 10000000 
for partial_package_4_count = 0 to partial_package_4_max: 
    -- Calculate how much we have already spent. 
    price = (full_package_4_count + partial_package_4_count) * 175 * (1-0.15) 

    -- Work out how many additional tickets we want. 
    x' = max(0, x - 5 * partial_package_count) 
    y' = max(0, y - 5 * partial_package_count) 
    z' = max(0, z - 5 * partial_package_count) 

    --- Add cost for additional tickets (with a 10% discount for every pack of 5) 
    price = price + x' mod 5 * 25 * (1-0.10) + x' div 5 * 5 
    price = price + y' mod 5 * 50 * (1-0.10) + x' div 5 * 10 
    price = price + y' mod 5 * 100 * (1-0.10) + x' div 5 * 20 

    if price < best_price 
     best_price = price 
     -- Should record other details about the current deal here too. 

Answer 3

Après avoir vendu le client autant de paquets complets que possible, nous nous retrouvons avec une N résiduelle de billets désirés de chacun des 3 types (5 $, 10 $, 20 $).Dans l'exemple que vous avez donné, les quantités désirées vont de 0 à 5 (6 valeurs possibles). Ainsi, il n'y a que 214 combinaisons résiduelles possibles (6 ** 3 - 2, moins 2 parce que les combinaisons 0-0-0 et 5-5-5 sont dégénérées). Juste pré-calculer le prix de chaque combinaison comme si elle avait été achetée sans le paquet 4; comparer ce calcul au coût du colis 4 (148,75 $); Cela vous indiquera l'approche la moins chère pour chaque combinaison.

Le nombre réel de colis est-il si important qu'un pré-calcul complet ne serait pas une approche viable?