动态规划呀-创新互联
文章目录
本文名称:动态规划呀-创新互联
网页路径:http://myzitong.com/article/hioed.html
- 01背包
- 二维数组
- 预备
- 初始化dp数组:
- 遍历背包,遍历
- 总代码
- 小改进
- 一维数组滚动优化
问题描述:
给定 n 件物品,物品的重量为 w[i],物品的价值为 v[i]。现挑选物品放入背包中,假定背包能承受的大重量为 c,问应该如何选择装入背包中的物品,使得装入背包中物品的总价值大?
首先输入共n个物品,一个容量为v的背包,n和v没有协同关系,只是制约关系
再输入[各物品重量,各物品价值]
分别存入重量数组与价值数组
本题以n,v=4,5 ,输入(1,2)(2,4)(3,4)(4,5)为例
N,V = map(int,input().split())
weight = []
val = []
for _ in range(N):
wi,vi = map(int,input().split())
weight.append(wi)
val.append(vi)
weight=[1,2,3,4]
value = [ 2,4,4,5]
dp = [ [0]*(V+1) for _ in range(N+1) ]
因为存在【没有物品,但有容量】与【有物品,容量不够】的情况,所以保留0数组
又因需要到达n,则range(N+1)
则五行六列
行:前4件物品
列:容量为1到5的书包
{ weight[i] , value[i] }与dp之间的关系:
dp通过 【i-1,{ 减weight[i] } + value[i]} 】 到达 下一个dp
for i in range(1,N+1):
for w in range(1,V+1):
if w
为什么是i-1呢?因为保留0的原因,导致i相比 与 相对应的 value大1,
总代码N,V = map(int,input().split())
weight = []
val = []
for _ in range(N):
wi,vi = map(int,input().split())
weight.append(wi)
val.append(vi)
dp = [[0]*(V+1) for _ in range(N+1)] # (N+1)*(V+1)
for i in range(N):
dp[i][0]=0
for i in range(1,N+1):
for w in range(1,V+1):
if w-weight[i-1]<0:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w-weight[i-1]]+val[i-1], dp[i-1][w])
print(dp[N][V])
小改进此时看着i-1比较别扭,则想一想能不能写出:
#取到i的weight[i],则剩下dp[i-1][w-weight[i]]
dp[i][w] = max(dp[i-1][w-weight[i]]+val[i], dp[i-1][w])
很因为保留0的原因,所以会显得二维数组的行列都大了1,想要对齐,就要在weight[]、value[]数组存入0,使对齐
改进后代码:
# N件物品,一个容量为V的背包
N,V = map(int,input().split())
weight = []
val = []
weight.append(0)
val.append(0)
for _ in range(N):
wi,vi = map(int,input().split())
weight.append(wi)
val.append(vi)
dp = [[0]*(V+1) for _ in range(N+1)] # (N+1)*(V+1)
for i in range(1,N+1):
for w in range(1,V+1):
if w-weight[i-1]<0:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w-weight[i]]+val[i], dp[i-1][w])
print(dp[N][V])
改进灵感来自听懂不翻车系列之–背包问题
一维数组滚动优化要从后往前覆盖才可以
暂时不学,现目标不需要节约空间
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
本文名称:动态规划呀-创新互联
网页路径:http://myzitong.com/article/hioed.html