c++ - 用给定面值的最少硬币数量来定额。贪婪的问题

Question

我有C++函数要做。它可以正常工作，但在某些情况下效果不佳-“贪婪问题”。

我的C++代码:

#include <vector>
#include <algorithm>

std::vector<int> ans;

std::vector<int> get_change(const std::vector<int> &denominations, int amount) {
    //pure algo
    std::vector<int> money = denominations;
    std::vector<int> count;
    ans.clear();
    count.assign(money.size(), 0);
    std::sort(money.begin(), money.end());
    int summ = amount;
    for (int i = count.size()-1; i >= 0; i--) {
        count[i] = summ / money[i];
        summ = summ % money[i];
        if (summ==0)
            break;
    }


    //ans generation
    for (int i = 0; i < money.size(); i++)
        for (int j = 0; j < count[i]; j++)
            ans.push_back(money[i]);
    return ans;
}

贪婪问题样本:get_change({ 1, 6, 9 }, 30)将返回{ 1, 1, 1, 9, 9, 9 }，但不返回{ 6, 6, 9, 9 }。

任务是改进此算法以获得相同的答案。

Answer 1

一种可能的方法是回溯。

回溯是一种通用算法，用于查找某些计算问题(尤其是约束满足问题)的所有(或某些)解决方案，该算法逐步为解决方案构建候选，并在确定候选对象无法解决问题时立即放弃候选(“回溯”)完成有效的解决方案。 (维基百科)

在这里，我们尝试确定每种硬币的硬币数量。

一旦硬币总数高于当前最佳解决方案，就会放弃候选人。而且，这里，在给定的情况下(在i步骤)，我们直接计算coins[i]的最大硬币数量，以使总和不高于该数量。

这是一个可能的实现:

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

std::vector<int> get_change(const std::vector<int>& denominations, int amount) {
    std::vector<int> coins = denominations;
    std::vector<int> n_coins(coins.size(), 0);
    std::vector<int> n_coins_opt(coins.size(), 0);
    int n = coins.size();

    std::sort(coins.begin(), coins.end(), std::greater<int>());

    int sum = 0;    // current sum
    int i = 0;      // index of the coin being examined
    int n_min_coins = amount / coins[n - 1] + 1;
    int n_total_coins = 0;
    bool up_down = true;

    while (true) {          // UP
        if (up_down) {
            n_coins[i] = (amount - sum) / coins[i];     // max number of coins[i]
            sum += n_coins[i] * coins[i];
            n_total_coins += n_coins[i];
            if (sum == amount) {
                if (n_total_coins < n_min_coins) {
                    n_min_coins = n_total_coins;
                    n_coins_opt = n_coins;
                }
                up_down = false;
                sum -= n_coins[i] * coins[i];
                n_total_coins -= n_coins[i];
                n_coins[i] = 0;
                i--;
            }
            else {
                if (i == (n - 1) || (n_total_coins >= n_min_coins)) {   // premature abandon
                    sum -= n_coins[i] * coins[i];
                    n_total_coins -= n_coins[i];
                    n_coins[i] = 0;
                    up_down = false;
                    i--;
                }
                else {
                    i++;
                }
            }

        }
        else {            // DOWN
            if (i < 0) break;
            if (n_coins[i] == 0) {
                if (i == 0) break;
                i--;
            }
            else {
                sum -= coins[i];
                n_coins[i] --;
                n_total_coins--;
                i++;
                up_down = true;
            }
        }
    }

    std::vector<int> ans;

    for (int i = 0; i < coins.size(); i++)
        for (int j = 0; j < n_coins_opt[i]; j++)
            ans.push_back(coins[i]);

    return ans;
}

int main() {
    std::vector<int> coins = { 1, 6, 9 };
    int amount = 30;
    auto n_coins = get_change(coins, amount);

    for (int i = 0; i < n_coins.size(); i++)
            std::cout << n_coins[i] << " ";

    std::cout << "\n";
    return 1;
}