钱币组合问题

经典背包问题的应用

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
    int money[] = {1, 5, 10, 20, 50, 100};
    int sum = 100;
    if (argc > 1) {
        sum = atoi(argv[1]);
    }
    vector<int> v(sum + 1, 0);
    v[0] = 1;
    for (int i=0; i<sizeof(money)/sizeof(int); ++i) {
        for (int j=money[i]; j<=sum; ++j) {
            v[j] = v[j] + v[j-money[i]];
        }
    }
    cout << v[sum] << endl;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背包问题具备的特征:给定一个target,target可以是数字也可以是字符串,再给定一个数组nums,nums中...
    _code_x阅读 1,459评论 0 2
  • Author: Richard Karp(1972) Abstract 有大量的计算问题涉及到确定无向图、有向图、...
    CureMarine阅读 1,316评论 0 0
  • 组合优化问题概念 从广义上讲,组合优化问题是涉及从有限的一组对象中找到"最佳"对象的问题。“最佳”是通过给定的评估...
    月月与阅读 9,972评论 0 1
  • 动态规划合集: 1.矩阵链乘法2.投资组合问题3.完全背包问题4.01背包问题5.最长公共子序列 例题2——投资问...
    Mereder阅读 1,370评论 0 1
  • 为什么要写这篇文章 排列组合问题在数学中占有重要的地位,其与概率论也有密切的关系。而且排列组合问题大量出现在求职笔...
    Haoqian阅读 2,714评论 0 5