[Algorithm] Money Change Problem (dynamic programming)

Question

Given a list of N coins, their values being in an array A[], return the minimum number of coins required to sum to S (you can use as many coins you want). If it's not possible to sum to S, return -1

Below are the solutions by "greedy" and "dynamic programming"

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

// greedy
int minCoins_greedy(vector<int> a, int sum) {

    sort(a.begin(), a.end(), greater<int>()); // sorted in descending order
    a.erase(unique(a.begin(), a.end()), a.end()); // remove duplicates

    int ret;
    for (int i = 0; i < a.size(); i  ) {
        int remains = sum - a[i];
        //cout << sum << " - " << a[i] << " = " << remains << endl;
        if (remains > 0) {
            ret = minCoins_greedy(a, remains);
            //cout << "ret: " << ret << endl;
            if (ret > 0) {
                cout << a[i] << "   ";
                return   ret;
            }
        } else if (remains == 0) {
            cout << a[i] << "   ";
            return 1;
        }
    }
    return -1;
}

// dynamic programming
#define MIN(a, b) ((a) == -1) ? (b) : min((a),(b));
int minCoins(vector<int> S, int sum) {

    int setSize = S.size();
    int count[setSize 1][sum 1];

    // For sum = 0, do not need any coins
    for (int i = 0; i < setSize 1; i  )
        count[i][0] = 0;

    // For empty set, it is impossible to sum to >0
    // use -1 represents fail
    for (int j = 1; j < sum 1; j  )
        count[0][j] = -1;

    /*
     * cost func:
     * c(n, m) = min( c(n-1, m) , c(n, m-M[n])   1 )
     *                ^^^^^^^^^   ^^^^^^^^^^^^^^^^
     *                don't take     take M[n]
     */
    for (int i = 1; i < setSize 1; i  ) {
        for (int j = 1; j < sum 1; j  ) {
            if ((j - S[i-1]) >= 0) {
                count[i][j] = MIN(count[i-1][j], count[i][j-S[i-1]]   1);
            }
            else
                count[i][j] = count[i-1][j];
        }
    }

    // uncomment this code to print table
    /*
    for (int i = 0; i <= setSize; i  )
    {
        for (int j = 0; j <= sum; j  )
            printf ("%4d", count[i][j]);
        printf("\n");
    }
    */

    return count[setSize][sum];
}


int main() {

    // Input to a sorted vector
    int size, sum;
    cout << "input 'size' and 'sum'" << endl;
    cout << "ex: 4 63" << endl;
    cin >> size >> sum;

    cout << "input coins" << endl;
    cout << "ex: 1 10 30 40" << endl;

    int* arr;
    arr = new int[size];
    for (int i = 0; i < size; i  ) {
        int c;
        cin >> c;
        arr[i] = c;
    }
    vector<int> vecArr(arr, arr size);

    // Output
    int out = minCoins(vecArr, sum);
    //int out = minCoins_greedy(vecArr, sum);

    cout << endl;
    if (out > 0)
        cout << "Minimum " << out << " coins needed" << endl;
    else
        cout << "Impossible" << endl;

    delete[] arr;

    return 0;
}

Ref

1. Wikipedia: Dynamic programming
2. Lecture 12: More about debugging, knapsack problem, introduction to dynamic programming
3. The 0/1 Knapsack Problem - Dynamic Programming Method
4. Dynamic Programming | Set 25 (Subset Sum Problem)
5. Money Changing Problem 之一