蓝桥杯(5):python动态规划DF[2:背包问题]

news/发布时间2024/7/21 10:18:57

1 0-1背包介绍【每件物品只能拿1件或者不拿】

1.1 简介

贪心是不可以的!!!

1.2 状态 及状态转移

转移解释:要么不选 则上一个直接转移过来【dp[i-1][j]】,要么是选这个之后体积为j 则上一个对应的就是【dp[i-1][j-wi] + v[i]】 选上这个之后价值叫上哦!!1

1.3 代码

n,v= list(map(int,input().split()))
w = [0]
value = [0]
for i in range(n):w_v = list(map(int,input().split()))w.append(w_v[0])value.append((w_v[1]))
# print(w)
# print(value)
'''容量总共为V
不超过v的时候价值最大
求最大价值--是矩阵中的值,那么还有两个指标分别是 物品数和容量
dp[i][j]表示前i个物品当体积为j时对应的价值''''''找到状态之后 想状态转移方程:
如果第i个物品不拿 dp[i][j] = dp[i-1][j]
如果第i个物品拿 dp[i][j] = dp[i-1][j-w[i]]+value[i]
要最大的价值 则选最大的 决定拿还是不拿'''
dp = [[0]*(v+1) for i in range(n+1)]
for i in range(1,n+1):for j in range(1,v+1):if j>=w[i]: # 说明存在第i个拿出来这种情况dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+value[i])else:dp[i][j] = dp[i-1][j]print(dp[n][v])

2 滚动数组优化

发现在上方的代码中 更新第i行只用到了i-1行的数据,所有可以把空间压缩为2

然后对代码做以下改变即可

3 完全背包【每件物品可以拿0件1件2件一直到无数件】

3.1 定义

每个物品可以不拿或者拿一件 两件。。。这样

有三个参数了现在,依次枚举i,j,k 三重循环时间代价太大了

怎么优化时间呢?

3.2 代码实现

n,v= list(map(int,input().split()))
w = [0]
value = [0]
for i in range(n):w_v = list(map(int,input().split()))w.append(w_v[0])value.append((w_v[1]))
# print(w)
# print(value)dp = [[0]*(v+1) for i in range(n+1)]
for i in range(1,n+1):for j in range(1,v+1):if j>=w[i]: # 说明存在第i个拿出来这种情况dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+value[i])else:dp[i][j] = dp[i-1][j]print(dp[n][v])

4 多重背包【0-1背包和完全背包的结合体】

4.1 定义

每种物品可是可以多拿但是有一个上限!!

不拿的情况也包含在上面的那个式子里了,所以更新值只需要 和自己比 留下最大的即可!!!

完全背包没有办法控制上限,所以我们只能老老实实的三重循环。。。

4.2 三重循环代码

n,v= list(map(int,input().split()))
w = [0]
value = [0]
s = [0]
for i in range(n):w_v_s = list(map(int,input().split()))w.append(w_v_s[0])value.append(w_v_s[1])s.append(w_v_s[2])
# print(w)
# print(value)
'''容量总共为V
不超过v的时候价值最大
求最大价值--是矩阵中的值,那么还有两个指标分别是 物品数和容量
dp[i][j]表示前i个物品当体积为j时对应的价值''''''找到状态之后 想状态转移方程:
如果第i个物品不拿 dp[i][j] = dp[i-1][j]
如果第i个物品拿 dp[i][j] = dp[i-1][j-w[i]]+value[i]
要最大的价值 则选最大的 决定拿还是不拿'''
dp = [[0]*(v+1) for i in range(n+1)]
for i in range(1,n+1):for j in range(1,v+1):for m in range(0, min(s[i],j//w[i])+1):# if j >= m*w[i]: # 说明存在第i个拿出来这种情况dp[i][j] = max(dp[i][j], dp[i-1][j-m*w[i]]+m*value[i])# 和0-1背包的区别就是dp[i-1][j-w[i]]变成了dp[i][j-w[i]]# else:#     dp[i][j] = dp[i][j]print(dp[n][v])

4.3 二进制优化后代码

新策略:二进制的拆si  !!!!!!!!!!!!!

普通拆发:

二进制的拆法:

##二进制优化
import sysdef put(_w, _v):for j in range(v, _w - 1, -1):dp[j] = max(dp[j], dp[j-_w] + _v)n, v = map(int, sys.stdin.readline().split())
dp = [0]*(v + 1)
for _ in range(n):weight, value, i = map(int, sys.stdin.readline().split())tmp = 1while i >= tmp:put(weight * tmp, value * tmp)i -= tmptmp <<= 1if i > 0:put(weight * i, value * i)
print(dp[v])

5 二维费用背包

5.1 定义

状态转移方程:

空间上受不了,用滚动数组

可以把i删掉

5.2 代码

N,V,M=map(int, input().split())
dp = [[0]*(M+1) for i in range(V+1)]for i in range(1,N+1):vi,mi,wi = map(int, input().split())for j in range(V,vi-1,-1):for k in range(M,mi-1,-1):#dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-vi][k-mi]+wi)dp[j][k] = max(dp[j][k], dp[j-vi][k-mi]+wi)
print(dp[V][M])

6 分组背包

很像01背包

'''
分组背包:
每组中只能选择一个物品
状态转移方程与0-1背包一样,唯一的区别是:在更新状态时要多与自己比较一次
不用一维滚动数组优化时,遍历顺序是每组,组中每个元素,背包容量
使用一维滚动数组优化时,遍历顺序是每组,背包容量,组中每个元素(可防止组中元素被选择多次)
'''##1、没有优化空间
N,V = map(int,input().split())
dp = [[0]*(V+1) for i in range(N+1)]
# dp[i][j]表示前i组物品体积不超过j的最大价值
#最终的答案dp[N][V]for i in range(1,N+1): # 对于每个组s = int(input())for q in range(s): # 对于每个组中的每个物品w,v = map(int,input().split())   #获取每个物品的质量与价值for j in range(0,V+1):   #对于当前背包容量if j< w:   #分组背包更新状态时,要比其他背包多一次比较,即要与本身做一次比较dp[i][j] = max(dp[i][j], dp[i-1][j])else:dp[i][j] = max(dp[i][j],dp[i-1][j],dp[i-1][j-w] + v)print(dp[N][V])#2.两行滚动数组优化N,V = map(int,input().split())
dp = [[0]*(V+1)for i in range(2)]for i in range(1,N+1):#对于每个组s = int(input())for _ in range(s): #对于每个组中的每个物品w,v = map(int,input().split())   #获取每个物品的质量与价值for j in range(1,V+1):   #对于当前背包容量if j< w:   #分组背包更新状态时,要比其他背包多一次比较,即要与本身做一次比较dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j])else:dp[i%2][j] = max(dp[i%2][j],dp[(i-1)%2][j],dp[(i-1)%2][j-w] + v)print(dp[N%2][V])#3 一维滚动数组优化 YYDS
N,V = map(int,input().split())
dp = [0]*(V+1)
for i in range(1,N+1):#对于每个组s = int(input())group =  []for _ in range(s): #对于每个组中的每个物品group.append([*map(int,input().split())])#分组包采用一维滚动数组时,需先遍历背包容量,再遍历每组每个物品的质量与价值,否则会出现一组中的物品被选择多次的情况for j in range(V,-1,-1):   #对于当前背包容量for w,v in group:   #获取每个物品的质量与价值if j>=w:  #背包容量不能小于物品质量,不然装不了#分组背包更新状态时,要比其他背包多一次比较,即要与本身做一次比较dp[j] = max(dp[j],dp[j-w] + v)
print(dp[V])

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.shwantai.cn/a/86656657.html

如若内容造成侵权/违法违规/事实不符,请联系万泰站长网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

营销中的归因人工智能

Attribution AI in marketing 归因人工智能作为智能服务的一部分&#xff0c;是一种多渠道算法归因服务&#xff0c;根据特定结果计算客户互动的影响和增量影响。有了归因人工智能&#xff0c;营销人员可以通过了解每个客户互动对客户旅程每个阶段的影响来衡量和优化营销和广告…

canvas画图,画矩形、圆形、直线可拖拽移动,可拖拽更改尺寸大小

提示&#xff1a;canvas画图&#xff0c;画矩形&#xff0c;圆形&#xff0c;直线&#xff0c;曲线可拖拽移动 文章目录 前言一、画矩形&#xff0c;圆形&#xff0c;直线&#xff0c;曲线可拖拽移动总结 前言 一、画矩形&#xff0c;圆形&#xff0c;直线&#xff0c;曲线可拖…

Python | Leetcode Python题解之第10题正则表达式匹配

题目&#xff1a; 题解&#xff1a; class Solution:def isMatch(self, s: str, p: str) -> bool:m, n len(s), len(p)dp [False] * (n1)# 初始化dp[0] Truefor j in range(1, n1):if p[j-1] *:dp[j] dp[j-2]# 状态更新for i in range(1, m1):dp2 [False] * (n1) …

Maplesoft Maple 2024(数学科学计算)mac/win

Maplesoft Maple是一款强大的数学计算软件&#xff0c;提供了丰富的功能和工具&#xff0c;用于数学建模、符号计算、数据可视化等领域的数学分析和解决方案。 Mac版软件下载&#xff1a;Maplesoft Maple 2024 for mac激活版 WIn版软件下载&#xff1a;Maplesoft Maple 2024特别…

【算法练习】28:选择排序学习笔记

一、选择排序的算法思想 弄懂选择排序算法&#xff0c;先得知道两个概念&#xff1a;未排序序列&#xff0c;已排序序列。 原理&#xff1a;以升序为例&#xff0c;选择排序算法的思想是&#xff0c;先将整个序列当做未排序的序列&#xff0c;以序列的第一个元素开始。然后从左…

c# wpf Template ContentTemplate

1.概要 1.1 定义内容的外观 2.2 要点分析 2.代码 <Window x:Class"WpfApp2.Window1"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schem…