1023 买书（完全背包问题求方案数）

￡神魔★判官ぃ 2022-09-11 02:14 131阅读 0赞

**1. 问题描述：**

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。问小明有多少种买书方案？（每种书可购买多本）

**输入格式**

一个整数 n，代表总共钱数。

**输出格式**

一个整数，代表选择方案种数。

**数据范围**

0 ≤ n ≤ 1000

输入样例1：  
20

输出样例1：  
2

输入样例2：  
15

输出样例2：  
0

输入样例3：  
0

输出样例3：  
1  
来源：[https://www.acwing.com/problem/content/1025/][https_www.acwing.com_problem_content_1025]

**2. 思路分析：**

分析题目可以知道这道题目的本质是**完全背包求解方案数**的问题，我们可以将总共的钱数n看成是背包的容量，书的价格看成是物品的体积，我们要求解的是恰好装满背包的方案数目，一开始时候我们可以定义一个二维数组或者列表dp，其中dp\[i\]\[j\]表示所有只从前i个物品中选，且总体积恰好是j的方案数目，怎么样进行状态的计算呢？状态计算对应集合的划分，一般是找最后一个不同点，我们可以按照最后一个物品i选择的数量进行集合的划分（可以参照下图），经过推导可以得到状态转移方程为dp\[i\]\[j\] = dp\[i - 1\]\[j\] + dp\[i\]\[j - v\]，dp\[0\]\[0\]表示一个合法方案， 所以我们在初始化的时候可以将dp\[0\]\[0\]初始化为1，这样在递推的时候最终的答案dp\[4\]\[n\]可以确保是从dp\[0\]\[0\]转移过来的，也即满足题目中恰好将n元钱花完这个条件。其实我们可以将空间优化为一维，我们只需要将其等价变形即可，可以发现进入到第二层循环的时候当前所有的dp\[j\]恰好就是上一层的所有状态（0，j），j - v小于j所以当前的dp\[j - v\]为当前这一层计算得到的结果，所以最终去掉第一维即可完成等价变形。为什么零一背包直接去掉第一维之后的结果是错误呢？因为零一背包对于当前的物品只能选或者不选，所以当前第i层使用的是第i - 1层的状态，所以我们在遍历的时候是不能够直接顺序遍历的，因为顺序遍历的时候dp\[j - v\]的状态是当前这一层计算出来的结果而我们需要使用到的是上一层的对应状态的结果所以结果就不正确了，所以在零一背包优化为一维的时候需要逆序遍历这样可以确保之前的状态是后面计算出来的，这样当前的dp\[j\]就不会使用到当前这一层dp\[j - v\]的状态了。完全背包问题可以选择当前的物品无限个，j - v使用到的是当前这一层计算得到的状态所以直接去掉第一维是正确的。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_15_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

**二维：**

if __name__ == '__main__':
        v = [0, 10, 20, 50, 100]
        n = int(input())
        dp = [[0] * (n + 1) for i in range(5)]
        # 没有钱的时候方案数目为1, dp[0][0]也是一个合法的方案
        dp[0][0] = 1
        for i in range(1, 5):
            # 注意这里不能够直接循环[v[i], n + 1]因为当j < v[i]的时候dp[i][j]需要使用到上一个状态而这些状态是合法的, 也即需要执行dp[i][j] = dp[i - 1][j]
            for j in range(n + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= v[i]:
                    dp[i][j] += dp[i][j - v[i]]
        print(dp[4][n])

**一维：**

if __name__ == '__main__':
        v = [10, 20, 50, 100]
        n = int(input())
        dp = [0] * (n + 1)
        # 没有钱的时候方案数目为1, dp[0]属于一个合法方案
        dp[0] = 1
        for i in range(4):
            # 在相加的时候dp[j]就是上一层对应的j, 而后面加的dp[j - v]就是当前这一层的j
            for j in range(v[i], n + 1):
                dp[j] += dp[j - v[i]]
        print(dp[n])

[https_www.acwing.com_problem_content_1025]: https://www.acwing.com/problem/content/1025/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/6790b3af444645c28049f71ebd1aedba.png