用给定面值的最少数量的硬币来指定金额。贪心问题

Question

我有 C++ 函数要做。它工作正常，但在某些情况下效果不佳 - "greedy problem".

我的 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)会return{ 1, 1, 1, 9, 9, 9 }，但不会{ 6, 6, 9, 9 }。

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

Answer 1

一种可能的方法是回溯。

回溯是一种通用算法，用于寻找某些计算问题的所有（或部分）解决方案，特别是约束满足问题，它会逐步构建解决方案的候选方案，并尽快放弃候选方案 ("backtracks")它确定候选人不可能完成有效的解决方案。（维基百科）

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

一旦硬币总数高于当前最优解，候选人就会被放弃。此外，这里，在给定的情况下（在步骤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;
}

Answer 2

这是一个 dynamic programming 问题。

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution{
    public static void main (String[] args) throws java.lang.Exception{
            System.out.println(getChange(new int[]{1,6,9},30));
            System.out.println(getChange(new int[]{1},3));
            System.out.println(getChange(new int[]{4,20,500},450));
    }

    private static List<Integer> getChange(int[] denominations,int amount){
            Arrays.sort(denominations);
            List<Integer> ans = new ArrayList<>();
            if(amount <= 0 || denominations[0] > amount) return ans;
            int[][] dp = new int[amount + 1][2];

            for(int i=0;i<denominations.length;++i){
                if(denominations[i] > amount) break;
                dp[denominations[i]][0] = 1;
                dp[denominations[i]][1] = 0;
                for(int j=denominations[i] + 1;j<=amount;++j){
                    if(dp[j-denominations[i]][0] > 0 && (dp[j][0] == 0 || dp[j-denominations[i]][0] + 1 < dp[j][0])){
                       dp[j][0] = dp[j-denominations[i]][0] + 1;
                       dp[j][1] = j-denominations[i];
                    }
                }
            }

            if(dp[amount][0] > 0){
                while(dp[amount][0] != 0){
                    ans.add(amount - dp[amount][1]);
                    amount = dp[amount][1];
                }
            }



            return ans;
    }
}

演示： https://ideone.com/2fYg4F

算法：

这类似于coin change问题。
我们先对数组中的数字进行排序，统一计算
现在，我们迭代所有数组元素并使每个数组元素循环遍历从该元素到最终数量的所有可能数量。
现在，如果我们已经总和 j - denominations[i]，我们只能 赚取金额 j（总和）。

同时，我们还会检查所需的最少硬币数量。如果当前 denominations[i] 的数量 j 需要比存储在 dp[j][0] 中的当前值更少的硬币，那么我们相应地更新 dp[j] 中的答案。

最后，我们只是遍历所需的确切硬币和 return 答案。

什么是dp[][]:

这只是一个简单的二维数组，其中第 0 列跟踪硬币的最小数量在它的第一个索引中需要，而 2^nd 索引具有给它的前一个硬币索引最小值。

dp[][] 中的 2^nd 索引将简化计算以找到确切的硬币价值，因为我们必须这样做 amount - dp[amount][1]获取币值。

最后，我们只检查 dp[amount][0] 值。如果它的值为 0，我们没有解，否则我们计算它。

Answer 3

我已将 vivek_23 的动态解决方案改编为所需的 C++ 语言。

std::vector<int> get_change2(const std::vector<int>& coins, int amount) {
    std::vector<int> denominations = coins;
    std::sort(denominations.begin(), denominations.end());
    std::vector<int> ans;

    if (amount <= 0 || denominations[0] > amount)
        return ans;

    int** dp = new int* [amount + 1];
    for (int i = 0; i < amount + 1; i++) {
        dp[i] = new int[2];
        dp[i][0] = 0;
        dp[i][1] = 0;
    }

    for (int i = 0; i < denominations.size(); i++) {
        if (denominations[i] > amount) break;
        dp[denominations[i]][0] = 1;
        dp[denominations[i]][1] = 0;
        for (int j = denominations[i] + 1; j <= amount; ++j) {
            if (dp[j - denominations[i]][0] > 0 && (dp[j][0] == 0 || dp[j - denominations[i]][0] + 1 < dp[j][0])) {
                dp[j][0] = dp[j - denominations[i]][0] + 1;
                dp[j][1] = j - denominations[i];
            }
        }
    }

    if (dp[amount][0] > 0) {
        while (dp[amount][0] != 0) {
            ans.push_back(amount - dp[amount][1]);
            amount = dp[amount][1];
        }
    }



    return ans;
}

用给定面值的最少数量的硬币来指定金额。贪心问题

Denominate the amount with the minimum number of coins with a given face value. Greedy problem

c++

algorithm

greedy

coin-change