2024蓝桥杯每日一题（背包）

备战2024年蓝桥杯 -- 每日一题
Python大学A组

        试题一：货币系统
        试题二：01背包问题
        试题三：完全背包问题

---

试题一：货币系统

【题目描述】

        给定 V 种货币（单位：元），每种货币使用的次数不限。不同种类的货币，面值可能是相同的。现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。

【输入格式】

        第一行包含两个整数 V 和 N。

        接下来的若干行，将一共输入 V 个整数，每个整数表示一种货币的面值。

【输出格式】

        输出一个整数，表示所求总方案数。

【数据范围】

        1≤V≤251,
        1≤N≤10000
        答案保证在long long范围内。

【输入样例】

3 10
1 2 5

【输出样例】

10

【解题思路】

        模板题

【Python程序代码】

v,n = map(int,input().split())
f = [0]*(n+10)
a = [0] + list(map(int,input().split()))
f[0]=1
for i in range(1,v+1):for j in range(a[i],n+1):f[j] += f[j-a[i]]
print(f[n])

---

试题二：01背包问题

【题目描述】
        有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

【输入格式】

        第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

        接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

【输出格式】

        输出一个整数，表示最大价值。

【数据范围】

        0<N,V≤1000
        0<vi,wi≤1000

【输入样例】

4 5
1 2
2 4
3 4
4 5

【输出样例】

8

【解题思路】

        模板题

【Python程序代码】

n,V = map(int,input().split())
a = []
for i in range(n):a.append(list(map(int,input().split())))
f = [0]*(V+10)
for v,w in a:for j in range(V,0,-1):if j>=v:f[j] = max(f[j], f[j-v]+w)
print(f[V])

---

试题三：完全背包问题

【题目描述】

        有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 v，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

【输入格式】

        第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

        接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

【输出格式】

        输出一个整数，表示最大价值。

【数据范围】

        0<N,V≤1000
        0<vi,wi≤1000

【输入样例】

4 5
1 2
2 4
3 4
4 5

【输出样例】

10

【解题思路】

        模板题

【Python程序代码】

n,V = map(int,input().split())
a = []
for i in range(n):a.append(list(map(int,input().split())))
f = [0]*(V+10)
for v,w in a:for j in range(v,V+1):f[j] = max(f[j],f[j-v]+w)
print(f[V])