Giảm thiểu giá cho các đơn đặt hàng giảm giá theo khối lượng

Question

Tôi đang cố gắng kết hợp một hệ thống để đề xuất các bộ dụng cụ tiêu hao dựa trên số lượng được yêu cầu. Thách thức tôi đang gặp phải là các bộ dụng cụ có giảm giá theo khối lượng/số lượng lớn, vì vậy có thể rẻ hơn cho khách hàng để đặt hàng với số lượng lớn hơn vì giá có thể ít hơn. Ví dụ, giả sử các bộ dụng cụ có sẵn là:

• 25 widget với $ 15
• 10 widget với $ 7
• 5 widget với $ 4
• 1 widget cho $ 1

Ngay bây giờ, với số lượng yêu cầu là 74, thuật toán của tôi sẽ đề xuất 2 x 25, 2 x 10 và 4 x 1 = 48 đô la. Tuy nhiên, sẽ rẻ hơn nếu khách hàng chỉ cần đặt hàng 3 x 25 = 45 đô la.

Bất kỳ suy nghĩ nào về cách giải quyết vấn đề này? Tôi đang viết mã bằng C#.

Cảm ơn!

Answer 1

Hình như DP chuẩn (lập trình động).

// 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; 
     } 
    } 
} 

Câu trả lời là min(bestPrice[74], bestPrice[74 + 1], ... bestPrice[74 + 25 - 1]). Overhead 25 - 1 rõ ràng là đủ, bởi vì nếu không bạn sẽ loại bỏ một gói và số tiền vẫn sẽ là >= 74.

Một số liên kết về chủ đề này:
http://en.wikipedia.org/wiki/Dynamic_programming
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

chỉnh sửa
Bạn có thể tìm giải pháp tối ưu nếu bạn sửa đổi nó một chút. Thêm lastPack mảng, do đó, lastPack[i] là kích thước của gói bạn đã sử dụng để đạt được số tiền i. Tôi đoán, bạn có thể tìm ra cách cập nhật mã giả ở trên.

Khi thuật toán kết thúc, bạn có thể nhận được giải pháp như thế này

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

Vâng, bắt đầu với đơn vị thứ 25, giá là $ 0,60/mặt hàng. Vì vậy, nếu khách hàng đặt hàng hơn 25, hãy quên các gói mà bạn đang tính toán và chỉ nhân số lượng lên $ 0,60.

Answer 3

Vì vậy, bạn đang thực sự sẽ phải tự xác định tất cả các breakpoint cho các hạng mục dưới một trật tự của 25. Sau đó, về cơ bản sử dụng một bảng tra cứu loại kịch bản để xác định những gì để đặt hàng cho qty nhỏ hơn 25. AS chỉ ra trước đây này là rất tương tự như vấn đề Knapsack.

Về cơ bản mã của bạn sẽ trông giống như;

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 

Bạn có thể sử dụng một số thuật toán tham lam để xác định nó khi đang di chuyển. Đó sẽ là lý tưởng nếu giá được kỳ vọng sẽ thay đổi rất nhiều.

Điều đó có thể trông giống như điền kích thước gói với đối sánh chính xác và sau đó xác định kết quả trùng khớp gần nhất với số lượng còn lại và xem liệu nó có rẻ hơn không.

Vì vậy, ví dụ:

//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; 
} 

Mã này là không có nơi gần hoàn thành nhưng phải cung cấp cho bạn một ý tưởng. Mã cũng có lẽ không phải là vĩ đại nhất.

Sửa

Các đoạn thứ hai của mã sẽ đi sau khi đoạn đầu tiên ở vị trí của lookup