d904: 換零錢 解題心得

題目來源：https://zerojudge.tw/ShowProblem?problemid=d904
USACO2007January Competition

一般人拿到這題後，會不自覺地從最大的硬幣開挑選，然後順著往下挑，按這思維往下，可以順利地拿到80%的分數，但最後兩題測資不會對，給一個測資讓大家參考：
93 5
60
31
5
2
1
在上面這組測資，如果先拿60，那麼最佳狀況為60+31+1+1，但如果先拿31則最佳狀況為31+31+31。
所以基本上這題大方向還是要用窮舉演算法，那麼我的選擇是DFS，當然過程中要做一些剪枝的動作來加速運算時間。
以下附上C++跟PYTHON的程式碼，有任何疑問都歡迎找我討論。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> v;
int n, m;
int minCount = 9999;

void dfs(int i, int count, int sum, int totalCount) {
    if (i == v.size()) return;
    sum += v[i] * count;
    //cout <<sum;
    totalCount += count;
    if (sum > n || totalCount > minCount) return;
    if (i + 1 == v.size() - 1) {
        if ((n - sum) % v[i + 1] == 0) {
            totalCount += (n - sum) / v[i + 1];
            sum = n;
        }
        else {
            return;
        }
    }
    if (sum == n) {
        if (minCount > totalCount) {
            minCount = totalCount;
        }
        return;
    }
    if (i == v.size() - 1) return;
    for (int k = i + 1; k < v.size(); k++) {
        if (n / v[k] < 0) continue;
        for (int j = 0; j <= n / v[k]; j++) {
            if (j + totalCount > minCount) break;
            dfs(k, j, sum, totalCount);
        }
        break;
    }
}

bool comp(const int& a, const int& b)
{
    return a > b;
}

int main()
{
    cin >> n >> m;
    while (m--) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end(), comp);
    int count = 0;

    for (int j = n / v[0]; j >= 0; j--) {
        dfs(0, j, 0, 0);
    }
    cout << minCount;

    return 0;
}

PYTHON：

mins = 99999

def dfs(sum , index , counts , target):
  global mins , cc
  sum += coins[index]
  #print(sum)
  counts += 1
  if counts >= mins:
    return
  elif sum == target:
    if mins > counts:
      mins = counts
    return
  else:
    for i in range(index , cc):
      if sum+coins[i] > target:
        continue
      dfs(sum , i , counts , target)




a = input().split(" ")
target = int(a[0])
cc = int(a[1])
coins = []
count = 0;
#count是這條路徑取的硬幣數
for i in range(cc):
  coins.append(int(input()))
coins.sort()
coins.reverse()
sum = 0
for i in range(cc):
  if sum+coins[i] > target:
    continue
  dfs(sum , i , count , target)

print(mins)