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])