대량 주문 할인 가격

Question

요청한 수량에 따라 소모품 키트를 제안하는 시스템을 구성하려고합니다. 제가 직면 한 과제는 키트에 대량/대량 할인이 있으므로 가격이 더 낮을 수 있기 때문에 고객이 대량 주문을하는 것이 더 저렴할 수 있습니다. , $ (7)

5 위젯 $ 1

위해 $ 4

1 위젯의 위젯 지금 $ (15)

10

• 25 위젯 : 예를 들어, 사용 가능한 키트는 가정 해 봅시다 요청 된 수량이 74 일 때, 내 알고리즘은 2 x 25, 2 x 10 및 4 x 1 = $ 48을 제안합니다. 그러나 고객이 단지 3 x 25 = $ 45를 주문하는 것이 더 저렴할 것입니다.

  이 문제를 해결하는 방법에 대한 의견이 있으십니까? 나는 C#으로 코딩하고있다.

  감사합니다.

Answer 1

표준 DP (동적 프로그래밍)와 비슷합니다.

// bestPrice is array of best prices for each amount 
// initially it's [0, INFINITY, INFINITY, INFINITY, ...] 

for (int i = 0; i <= 74; ++i) { 
    for (Pack pack : packs) { 
     // if (i + pack.amount) can be achieved with smaller price, do it 
     int newPrice = bestPrice[i] + pack.price; 
     if (newPrice < bestPrice[i + pack.amount]) { 
      bestPrice[i + pack.amount] = newPrice; 
     } 
    } 
} 

대답은 min(bestPrice[74], bestPrice[74 + 1], ... bestPrice[74 + 25 - 1])입니다. 오버 헤드 25 - 1은 분명히 충분합니다. 그렇지 않으면 한 팩을 지울 것이고 금액은 여전히 ​​>= 74이 될 수 있습니다. 주제에

일부 링크 : 당신이 그것을 조금 수정하면 당신은 최적의 솔루션을 찾을 수 있습니다

http://en.wikipedia.org/wiki/Dynamic_programming
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

편집. lastPack 어레이를 추가하십시오. 따라서 lastPack[i]은 금액이 i 인 패키지의 크기입니다. 위의 의사 코드를 업데이트하는 방법을 알 수 있습니다.

알고리즘이 완료되면, 당신은이

int total = 74; 
while (total > 0) { 
    // package of size lastPack[total] was used to get amount 'total' 
    // do whatever you want with this number here 

    total -= lastPack[total]; 
} 

Answer 2

글쎄, 25 번째 단위부터 가격은 $ 0.60/item입니다. 고객이 25 이상을 주문하는 경우 계산중인 패키지를 잊어 버리고 수량에 $ 0.60을 곱하면됩니다.

Answer 3

같은 솔루션은 그래서 당신이 실제로 그런 기본적으로 조회 테이블을 사용하여 수동으로 (25)의 순서에 따라 항목에 대한 중단 점을 모두 결정해야 할 것 얻을 수 있습니다 type 시나리오를 사용하여 25 미만의 수량을 주문해야하는지 결정합니다. 이전에 지적했듯이 이는 배낭 문제와 매우 유사합니다.

기본적으로 코드는 다음과 유사합니다.

int qtyOrder; 
int qtyRemain; 
int qty25pack; 
int qty10pack; 
int qty5pack; 
int qty1pack; 

//Grab as many 25 packs as possible 
qty25pack = (qtyOrder % 25); 
qtyRemain -= qty25Pack * 25; 

//Here use your lookup table to determine what to order 
// for the qty's that are less than 25 

당신은 어떤 종류의 욕심 많은 알고리즘을 사용하여 즉시 판단 할 수 있습니다. 가격이 많이 바뀔 것으로 예상되면 이상적입니다.

정확히 일치하는 패키지 크기를 채우고 남아있는 수량보다 조금 더 가까운 가장 가까운 일치를 결정하고 더 싼지 확인할 수 있습니다.

그래서 예를 들면

:

//find the perfect product amount price 
While (qtyRemain != 0) { 
perfectPrice += (qtyRemain % nextSmallestSize) * nextSmallestPackagePrice; 
qtyRemain -= (qtyReamin % nextSmallestSize) 
} 

//Find the closest match over price 
While ((qtyRemain % nextSmallestSize) != 0){ 
closePrice += (qtyRemain % nextSmallestSize) * nextSmallestPackagePrice; 
qtyRemain -= (qtyRemain % nextSmallestSize) 
} 
//add the last price before we reached the perfect price size 
closePrice += nextSmallestPackagePrice; 

//determine lowest price 
if closePrice < perfectPrice { 
cost = closePrice; 
} 
else { 
cost = PerfectPrice; 
} 

이 코드가 완료 근처에 어디 없지만 당신에게 아이디어를 줄 것이다. 코드도 아마도 가장 위대한 것은 아닙니다.

편집

코드의 두 번째 덩어리는 당신이 더 많은 상품을 주문할 수 있습니다 경우 판매자는 당신에게 낮은 가격을 줄 것이다 확신 조회