C++---背包模型---货币系统1（每日一道算法2023.3.21）
创始人
2025-05-31 17:21:19
0次
注意事项：
本题为"dp动态规划—完全背包"的扩展题，和“背包模型—买书”的解法基本相同，dp思路和优化思路这里就不多讲。
题目：
给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。
输入格式
第一行，包含两个整数n和m。
接下来n行，每行包含一个整数，表示一种货币的面值。
输出格式
共一行，包含一个整数，表示方案数。
数据范围
n≤15,m≤3000
输入:
3 10
1
2
5
输出：
10
#include
#include
#include
#include
using namespace std;typedef long long LL;
const int N = 3010;
int n, m;
int v[N];
LL f[N][N]; //需要开long long，否则爆int，具体原因是可以看作是组合数问题来求，C15 3000，遇到最坏情况long long也会爆掉int main() {cin >> n >> m;for (int i =1; i<=n; i++) cin >> v[i];f[0][0] = 1; //选0个面值总和为0的方案也算一个方案//朴素版完全背包，这里可以优化为一维双循环，具体看完全背包那篇文章，有详解for (int i = 1; i<=n; i++) {for (int j = 0; j<=m; j++) {for (int k = 0; k*v[i]<=j; k++) {f[i][j] += f[i-1][j-k*v[i]];}}}cout << f[n][m];return 0;
} 思路：
这道题唯一需要注意的点就是数据范围，可以用组合数的方式来算出来最坏情况下应该是C(15, 3000)，long long都存不下，还好数据卡的不是那么死（
如果有所帮助请给个免费的赞吧~有人看才是支撑我写下去的动力！
声明：
算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流
相关内容
热门资讯
最新或2023（历届）异地办理...
最新或2023（历届）异地办理身份证流程,多地已实施异地办身份证 此外，天津与河南、江苏与安徽、浙江...
最新或2023（历届）特卖会邀...
特卖会邀请函亲爱的各位邻居：根据大家之前的要求和反馈，咱们组织了宁波50余建材家具家电的品 牌联盟活...
最新或2023（历届）体育活动...
体育活动邀请函范文尊敬的各位爱心网友、博友：多年来，您们对慈善公益事业、弱势群众的真诚关注、关怀，让...
最新或2023（历届）体育活动...
体育活动邀请函模板尊敬的家长朋友：您好！身处在大数据时代与经济全球化背景下，考高分、拼高考已不再是成...
最新或2023（历届）讨论会邀...
讨论会邀请函各位师兄：大家好！12月8日至10日，由北京佛教居士林与北京广化寺联合主办，佛教在线承办...
最新或2023（历届）体验邀请...
体验邀请函尊敬的最新或2023（历届）***************体验会现场将展示********...
最新或2023（历届）体育比赛...
体育比赛邀请函范文尊敬的家长朋友：为实现学校、家庭、社会三维一体的有机整合，让家长进一步了解学校的办...
最新或2023（历届）体育活动...
体育活动邀请函尊敬的家长朋友：您好！身处在大数据时代与经济全球化背景下，考高分、拼高考已不再是成功的...
最新或2023（历届）体育比赛...
体育比赛邀请函各位领导、各位来宾、裁判员、运动员、同志们： 今天，我们在这里隆重举行枝江市“电力杯”...
最新或2023（历届）体验活动...
尊敬的家长朋友：您好！身处在大数据时代与经济全球化背景下，考高分、拼高考已不再是成功的唯一标志。对于...
最新或2023（历届）调研活动...
调研活动邀请函先生/女士：您好!##我们是安徽先生信国际市场研究有限公司，是一家##专业的汽车市场研...
最新或2023（历届）同乡会聚...
同乡会聚餐邀请函经同乡会第二次理事会商议决定，于9月15日举行中秋联谊活动。此次联谊会是希望在昆明的...
最新或2023（历届）调研座谈...
调研座谈会邀请函尊敬的贵宾：当前煤炭行业正处在推进市场化改革的关键时期，进一步完善煤炭价格形成机制的...
最新或2023（历届）调研邀请...
调研邀请函范文饲料行业人力资源管理者：您好!太和顾问诚邀贵公司参加“最新或2023（历届）度饲料行业...
最新或2023（历届）体智能亲...
体智能亲子活动邀请函亲爱的朋友们：五月五，是端午；插艾叶，挂香囊；五彩线，手腕绑；吃粽子，沾白糖；龙...
学术会议邀请函范文大全 wor...
【学术会议邀请函范文大全一】 尊敬的 教授 您好! 由中华中医药学会络病分会主办，河南省中医药...
大学学术会议邀请函 大学学术会...
大学学术会议邀请函【一】 由中华医学会航空航天医学分会暨空军飞行人员健康鉴定专业委员会主办的全...
学术会议邀请函格式范文 学术会...
学术会议邀请函格式 一、寄信人地址、日期。 二、收信人及其地址。 三、尊称：Dear X X ...
医院学术会议邀请函 医院学术会...
医院学术会议邀请函尊敬的主任： 为促进扬州康复事业的发展，加强扬州康复医学领域与外界的学术交流，了...
客户会议邀请函 客户会议邀请函...
客户会议邀请函(一)兹邀请： 参加苏州园发企业管理咨询有限公司在苏州举办的20XX年新年园发客...