1021 货币系统(完全背包问题求方案数) 秒速五厘米 2022-09-11 04:24 91阅读 0赞 **1. 问题描述:** 给你一个n种面值的货币系统,求组成面值为m的货币有多少种方案。 **输入格式** 第一行,包含两个整数n和m。接下来n行,每行包含一个整数,表示一种货币的面值。 **输出格式** 共一行,包含一个整数,表示方案数。 **数据范围** n ≤ 15,m ≤ 3000 **输入样例:** 3 10 1 2 5 **输出样例:** 10 来源:[https://www.acwing.com/problem/content/description/1023/][https_www.acwing.com_problem_content_description_1023] **2. 思路分析:** 分析题目可以知道我们需要选择一些面值的货币,求解使得这些货币最终恰好能够组成面值为m的方案数目;每种面值的货币都是可以选择无限次的,所以属于经典的**完全背包求解方案数目**的问题,可以将货币看成是物品,构成面值为m可以看成背包的容量为m,与acwing[1023][]买书的题目是一模一样的;完全背包问题属于动态规划中的经典问题,对于动态规划的问题主要有两个步骤:① 状态表示 ② 状态计算;我们一开始可以定义一个二维数组,其中dp\[i\]\[j\]表示前i个物品中背包容量恰好为j的方案数目,对于背包容量"恰好"的题目我们在初始化的时候是将第一个状态值置为1,例如在一维数组的时候一般是dp\[0\] = 1;完全背包问题的二维状态转移方程为dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - v\],其实我们可以将二维数组优化为一维数组,优化的过程其实一个等价变形的过程,可以发现状态转移方程中的dp\[i - 1\]\[j\]为上一层循环对应的状态值,dp\[i\]\[j - v\]为当前这一层循环对应的状态值,优化为一维之后状态转移方程为dp\[j\] += dp\[j - v\],一开始进入循环的时候dp\[j\]属于上一层循环对应的状态值,而dp\[j - v\]小于j所以在遍历到j的时候j - v的状态已经在当前这一层循环计算过了所以dp\[j - v\]为当前这一层循环对应的状态值,恰好满足顺序遍历的要求,所以对于完全背包问题来说直接去掉第一维即可完成等价变形(对于一维的零一背包则需要逆序遍历才可以完成等价变形)。 **3. 代码如下:** if __name__ == '__main__': n, m = map(int, input().split()) dp = [0] * (m + 1) dp[0] = 1 for i in range(n): v = int(input()) # 顺序枚举体积 for j in range(v, m + 1): dp[j] += dp[j - v] print(dp[m]) [https_www.acwing.com_problem_content_description_1023]: https://www.acwing.com/problem/content/description/1023/ [1023]: https://blog.csdn.net/qq_39445165/article/details/120229358
还没有评论,来说两句吧...