대량 할인 가격을 적용하는 알고리즘

Question

나는 중국인 경매 웹 사이트를 디자인하고 있습니다.

티켓 ($ 5, $ 10 & $ 20)은 개별적으로 또는 할인을받을 수있는 패키지를 통해 판매됩니다. 다양한 티켓 패키지는 예를 들어이 있습니다

1. 5- $ (5) 티켓 =는
10 % 할인을받을
2. 5- $ (10) 티켓 =이
10 % 할인을받을
3. 5- $ (20) 티켓 =는
10 % 할인을받을 수 사용자가 장바구니에 티켓을 추가하면
4. 5- $ (5) 티켓 + 5- $ (10) 티켓 + 5- $ (20) 티켓 = 내가 그들에게 줄 수있는 저렴한 패키지 (들)을 파악해야

15 % 할인을받을 수 있습니다. 트릭은 사용자가 4- $ 5 티켓 + 5- $ 10 티켓 + 5- $ 20 티켓을 추가하면 패키지 4를 줄 수 있다는 것입니다. 왜냐하면 그 티켓이 가장 저렴하기 때문입니다.

이 문제를 해결하는 알고리즘이나 팁을 얻는 데 도움이된다면 크게 도움이 될 것입니다.

감사

편집

내가 대답, 감사 모두를 생각하지만, 코드가 깁니다.

누군가가 여전히 관심이있는 경우 답변 코드를 게시합니다.

Answer 1

하나의 접근법은 동적 프로그래밍입니다.

구매자가 아이템 A의 x와 아이템 B의 y, 아이템 C의 Z를 원할 경우, 0 세배 (x ', y', z ')의 값을 0으로 계산해야한다는 아이디어가 있습니다. < = x '< = x 및 0 < = Y'< Y = 0 < = Z '< = Z 적어도 X 얻는 가장 저렴한 방법'A의를, Y 'B 및 z의'의 C. 의사 코드 :

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 

그러면 next_package가 나타내는 패키지를 장바구니에 추가하여 (x, y, z)에서 뒤로 작업 할 수 있습니다.

많은 종류의 항목이 있거나 각 항목이 많으면 분기 및 바인딩이 더 나은 선택 일 수 있습니다.

Answer 2

먼저 필요한 전체 패키지 4 개를 계산하십시오. 방해가되지 않도록하십시오.

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 

실제로 많은 티켓을 구매하고 싶지는 않지만 패키지 4를 구입할 가치가 있습니다.

몇 명이나 될 수 있습니까?

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

이제 루프가 이들 각각을 시도 :

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

을 고객에게 가능한 한 많은 완전한 패키지를 판매 후, 우리는 3 가지의 각각의 원하는 티켓의 일부 잔여 N 남아 있습니다 (5 달러, 10 달러, 20 달러).예를 들어, 원하는 수량은 0에서 5까지입니다 (6 개의 가능한 값). 따라서, 조합 0-0-0과 5-5-5가 퇴보하기 때문에 단지 214 개의 가능한 잔여 조합 (6 ** 3 - 2; 2 빼기)이있다. 패키지 4없이 구매 한 것처럼 각 조합의 가격을 미리 계산하면됩니다. 그 계산을 패키지 4의 비용 ($ 148.75)과 비교하십시오. 이렇게하면 모든 조합에 대해 가장 저렴한 접근 방식을 알 수 있습니다.

패키지의 실제 수가 너무 커서 완전한 사전 계산이 실행 가능한 접근 방식이되지 않을 수 있습니까?