[ create a new paste ] login | about

Link: http://codepad.org/S3S4nDbr    [ raw code | output | fork | 1 comment ]

mohit_at_codepad - C++, pasted on Mar 14:
// http://d.hatena.ne.jp/Nabetani/20111206/p1


#include <iostream>
#include <map>
#include <cstdlib>

std::map<int, int> best;
int total, otsuri;

int value_of(std::map<int,int> coins) {
    int value = 0;
    for(std::map<int,int>::iterator it = coins.begin(); it != coins.end(); ++it) value += it->first * it->second;
    return value;
}

void pay(std::map<int, int> coins) {
    if(!otsuri) return;
    const int value = value_of(coins);
    if(value < total) return;
    const int change = value - total;
    if(change < otsuri) {
        best = coins;
        otsuri = change; 
    }
    for(std::map<int, int>::iterator it = coins.begin(); it != coins.end(); ++it) {
        if(it->second) {
            --it->second; pay(coins); ++it->second;
        }
    } 
}

// Assumption: all numbers are positive
// Amount to pay is not zero
int main(int argc, char *const *argv) {
    std::map<int, int> coins;
    if(argc < 3) {
      // dummy sample
      otsuri =  total = 100;
      for(int i = 2; i < 5; ++i) coins[i*17]++;
    } else {
      otsuri =  total = atoi(argv[1]);
      for(int i = 2; i < argc; ++i) coins[atoi(argv[i])]++;
    }
    pay(coins);
    if( best.empty() ) std::cout << "Can not pay" << std::endl;
    else {
        std::cout << "Total : " << total << ", pay : [";
        int ncoin = 0;
        for(std::map<int, int>::iterator it = best.begin(); it != best.end(); ++it) ncoin += it->second;
        for(std::map<int, int>::iterator it = best.begin(); it != best.end(); ++it)
        for(int i = 0; i < it->second; ++i) std::cout << it->first << (--ncoin ? ',' : ']');
        std::cout << ", Change : " << otsuri << std::endl;
    } 
    return 0;
}


Output:
1
Total : 100, pay : [34,68], Change : 2


Create a new paste based on this one


Comments:
posted by mohit_at_codepad on May 20
Function value_of should be inline
And the type of argument coins should be "const std::map<int,int> &"
reply