蓝桥杯Python-A组备战记录-day1

PYTHON常用函数

map()函数

map() 会根据提供的函数对指定序列做映射。

第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表。

map() 函数语法：

map(function, iterable, ...)
## function -- 函数
## iterable -- 一个或多个序列

实例：

a = [1,2,3,4,5]
b = list(map(lambda x: x ** 2, a))
print(b)
## 结果
[1, 4, 9, 16, 25]

## 在写算法题的时候map函数主要用于对读入的数据进行类型转换
## 如
a = input().split()
b = list(map(int, a))
print(a)
print(b)
## 结果
1 2 3 4
['1', '2', '3', '4']
[1, 2, 3, 4]

split() 函数

Python split() 通过指定分隔符对字符串进行切片，如果参数 num 有指定值，则分隔 num+1 个子字符串

split() 函数语法：

str.split(str="", num=string.count(str)).
## str -- 分隔符，默认为所有的空字符，包括空格、换行(\n)、制表符(\t)等。
## num -- 分割次数。默认为 -1, 即分隔所有。
# 实例
str = "hello python world !"
print (str.split())
print (str.split(' ', 1 ))
# 输出
['hello', 'python', 'world', '!']
['hello', 'python world !']

题目尝试

01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i件物品的体积是 Vi，价值是 Wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

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

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

输出格式

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

输出样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

代码

n, v = map(int, input().split())
goods = []
for i in range(n):
    goods.append([int(i) for i in input().split()])
print(goods)

# 初始化，先全部赋值为0，这样至少体积为0或者不选任何物品的时候是满足要求  
dp = [[0 for i in range(v+1)] for j in range(n+1)]

for i in range(1, n+1):
    for j in range(1,v+1):
        dp[i][j] = dp[i-1][j]  # 第i个物品不选
        if j>=goods[i-1][0]:# 判断背包容量是不是大于第i件物品的体积
            # 在选和不选的情况中选出最大值
            dp[i][j] = max(dp[i][j], dp[i-1][j-goods[i-1][0]]+goods[i-1][1])


print(dp[-1][-1])