动态规划呀-创新互联

文章目录
  • 01背包
    • 二维数组
      • 预备
      • 初始化dp数组:
      • 遍历背包,遍历
      • 总代码
      • 小改进
    • 一维数组滚动优化

创新互联自2013年创立以来,先为格尔木等服务建站,格尔木等地企业,进行企业商务咨询服务。为格尔木企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。01背包 二维数组

问题描述:
给定 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数组:

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://pwwzsj.com/article/hioed.html