动态规划呀-创新互联
文章目录
当前名称：动态规划呀-创新互联
当前网址：http://6mz.cn/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://6mz.cn/article/hioed.html