1021 货币系统（完全背包问题求方案数）

秒速五厘米 2022-09-11 04:24 139阅读 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