四川盐亭网站制作公司

动态规划呀-创新互联

文章目录
  • 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://scyanting.com/article/hioed.html

其他资讯