Đối với một số tiền nhất định, hãy giảm thiểu số lượng ống đồng xu nếu tất cả các ống giữ 64 nhưng không cần phải được điền

Question

Chỉnh sửa: Nếu ai đó có thể cung cấp câu trả lời đệ quy (liên kết) thay đổi vấn đề này sẽ giúp một LOT

---

Với một số tiền nhất định, hãy giảm thiểu số lượng ống đồng xu nếu tất cả các ống có thể chứa 64 xu.

mỗi ống CHỈ có thể giữ một loại tiền xu duy nhất.

mỗi ống KHÔNG cần phải được điền đầy đủ.

---

ví dụ: cho tiền xu American số tiền sẽ là $ 0.01, $ 0.05, $ 0.10, $ 0.25, $ 0.50, và $ 1.00

6 cent có thể được thực hiện như 6 1cent tiền xu trong một ống duy nhất,

25 cent có thể là một ống với một đơn 25c tiền xu hoặc một ống với năm đồng tiền 5c.

65 xu sẽ được thực hiện dưới dạng 13 xu, vì 65 xu 1c sẽ cần sử dụng 2 ống.

---

Tôi đang cố gắng viết một plugin Minecraft, và tôi gặp rất nhiều khó khăn với thuật toán này.

Answer 1

một cái gì đó như thế này:

a[0] = 100; //cents 
a[1] = 50; a[2] = 25; a[3] = 10; a[4] = 5; a[5] = 1; 

cnt[6]; //array to store how much coins of type i you use; 


void rec(sum_left, p /* position in a array */) { 
    if (p == 5) { 
     cnt[5] = sum_left; 
     //count how many tubes are used by cnt array, update current answer if neccessary; 
     return; 
    } 
    for (int i = 0; i <= sum_left/a[p]; i++) 
     //take i coins of type a[p] 
     rec(sum_left - i*a[i], p+1); 
} 

int main() { 
    rec(sum, 0); 
} 

Answer 2

Một bảng tra cứu là một phương pháp tốt.

int[] Coins = new[] { 100, 50, 25, 10, 5, 1 }; 
int[,] Table = new int[6,6400]; 

/// Calculate the number of coins of each type that minimizes the number of 
/// tubes used. 
int[] Tubes(int cents) 
{ 
    int[] counts = new int[Coins.Length]; 
    if (cents >= 6400) 
    { 
     counts[0] += (cents/6400) * 64; // number of coins in filled $1-tubes 
     cents %= 6400; 
    } 
    for (int i = 0; i < Coins.Length; i++) 
    { 
     int count = Table[i, cents]; // N coins in (N + 63)/64 tubes 
     counts[i] += count; 
     cents -= count * Coins[i]; 
    } 
    return cents; 
} 

Để tính bảng, bạn có thể sử dụng này:

void CalculateTable() 
{ 
    for (int i = Coins.Length-1; i >= 0; i--) 
    { 
     int coin = Coins[i]; 
     for (int cents = 0; cents < 6400; cents++) 
     { 
      if (i == Coins.Length-1) 
      { 
       // The 1 cent coin can't be divided further 
       Table[i,cents] = cents; 
      } 
      else 
      { 
       // Find the count that minimizes the number of tubes. 
       int n = cents/coin; 
       int bestTubes = -1; 
       int bestCount = 0; 
       for (int count = cents/coin; count >= 0; count--) 
       { 
        int cents1 = cents - count * coin; 
        int tubes = (count + 63)/64; 
        // Use the algorithm from Tubes() above, to optimize the 
        // lesser coins. 
        for (int j = i+1; j < Coins.Length; j++) 
        { 
         int count1 = Table[j, cents1]; 
         cents1 -= count1 * Coins[j]; 
         tubes += (count1 + 63)/64; 
        } 
        if (bestTubes == -1 || tubes < bestTubes) 
        { 
         bestTubes = tubes; 
         bestCount = count; 
        } 
       } 
       // Store the result 
       Table[i,cents] = bestCount; 
      } 
     } 
    } 
} 

CalculateTable chạy trong một vài mili giây, vì vậy bạn không cần phải lưu nó vào đĩa.

Ví dụ:

Tubes(3149) -> [ 31, 0, 0, 0, 0, 49] 
Tubes (3150) -> [ 0, 63, 0, 0, 0, 0] 
Tubes (31500) -> [315, 0, 0, 0, 0, 0] 

Những con số có nghĩa là số tiền xu. N đồng tiền có thể được đưa vào (N + 63)/64 ống.

Answer 3

Dưới đây là một thuật toán recursive, heuristic và greedy.

Trong mảng T, mỗi T[i] chứa một mảng gồm 6 số nguyên.

Nếu số tiền đã cho là 65 thì bạn gọi tubes(65) và sau đó print T[65].

coins[1..6] = {1, 5, 10, 25, 50, 100} 

tubes(sum) 
    if sum < coins[1] 
     return 
    for i = 1 to 6 
     tubes(sum - coins[i]) 
    best-tubes[1..6] = {64, 64, 64, 64, 64, 64} 
    for i = 1 to 6 
     if sum - coins[i] >= 0 
      current-tubes[1..6] = copy of T[sum - coins[i]] 
      if current-tubes[i] < 64 
       current-tubes[i] += 1 
       if current-tubes is better than best-tubes* 
        best-tubes = current-tubes 
    T[sum] = best-tubes 

Để bao la cải thiện thời gian chạy, bạn có thể kiểm tra xem hiện tại T[sum] đã được đánh giá. Việc thêm kiểm tra này sẽ hoàn thành cách tiếp cận được gọi là dynamic programming.

* current-tubes is better than best-tubes đang sử dụng ít ống hơn, hoặc sử dụng cùng số lượng ống có ít tiền hơn hoặc sử dụng cùng số ống nhưng ống giữ giá trị lớn hơn. Đây là phần tham lam trong hành động.