Bài toán Đổi Tiền Tối Thiểu (Greedy)

Giới thiệu

Cho một tập đồng xu C(c1, c2, ..., cn) và một giá trị V. Bài toán yêu cầu sử dụng số lượng đồng xu tối thiểu để đổi ra giá trị V.

Lưu ý: Giả sử có số lượng đồng xu không giới hạn cho mỗi mệnh giá.

Ví dụ: với tập đồng xu {1, 2, 5, 10} và giá trị 22, ta chọn {10, 10, 2} - 3 đồng xu.

Độ phức tạp: O(V), trong đó V là giá trị cần đổi.

Chú ý: Giải pháp tham lam này chỉ đúng với một số hệ đồng xu nhất định (như tiền Việt Nam). Với hệ đồng xu tùy ý, cần dùng quy hoạch động.

Đầu vào và Đầu ra

Đầu vào: Giá trị, ví dụ 47
Đầu ra: Enter value: 47
Coins are: 10, 10, 10, 10, 5, 2

Thuật toán

findMinCoin(value)

Đầu vào: Giá trị cần đổi

Đầu ra: Tập hợp các đồng xu

Begin
  tập coins := {1, 2, 5, 10}
  với mọi đồng xu i từ giá trị cao đến thấp làm:
    trong khi value >= coins[i] làm:
      value := value - coins[i]
      thêm coins[i] vào danh sách kết quả
    done
  done
  in tất cả phần tử trong danh sách đồng xu.
End

Ví dụ (C++)

#include <iostream>
#include <list>
#define COINS 4
using namespace std;

float coins[COINS] = {1, 2, 5, 10};

void findMinCoin(int cost) {
  list<int> coinList;
  for(int i = COINS - 1; i >= 0; i--) {
    while(cost >= coins[i]) {
      cost -= coins[i];
      coinList.push_back(coins[i]);  // thêm đồng xu vào danh sách
    }
  }
  list<int>::iterator it;
  for(it = coinList.begin(); it != coinList.end(); it++) {
    cout << *it << ", ";
  }
}

int main() {
  int val;
  cout << "Enter value: ";
  cin >> val;
  cout << "Coins are: ";
  findMinCoin(val);
  cout << endl;
}

Kết quả đầu ra

Enter value: 47
Coins are: 10, 10, 10, 10, 5, 2