浅析python实现动态规划背包问题

一个包可以背4kg的东西，现在有四件东西，重量分别为1kg，4kg，3kg，1kg，价值为：1500,3000,2000,2000；

现在要求你，在包里背的东西价值最大，但是不能超过背包的最大载重量

#几件物品的重量
w = [0,1,4,3,1]
#几件物品的价值
v= [0, 1500, 3000, 2000, 2000]
#物品数量
n = len(w) - 1
#包的载重量
m = 4

#建立一个列表表示在包中的物品，元素是True时代表对应元素放入
x = []
#放入包中的总价值
value = 0
#建立一个矩阵，来表示在前i个物品中，当载重量是j时，放入包中的最大价值，table[i][j]
table = [[0 for i in range(m+1)] for j in range(n+1)]

def dynamic(w,v,n,m,x):
 #计算table矩阵
 for i in range(1, n+1): #代表物品一件一件的考虑
  for j in range(1, m+1):  #代表子背包的大小一点一点的考虑
   if (j >= w[i]): #当背包的大小大于物品的重量时，考虑放进去
    table[i][j] = max(table[i-1][j], table[i-1][j-w[i]] + v[i])
   else:
    table[i][j] = table[i -1][j] #如果放不进去，就继承之前的价值

 #递推装入背包中的物体，寻找跳变的地方，从最后结果开始逆推
 j = m
 for i in range(n, 0, -1):
  if table[i][j] > table[i- 1][j]: #如果多加一件物品之后，价值增大，就将这一件物品加入列表中
   x.append(i)
   j = j - w[i] #此时为剩余背包的载重量

 #返回最大价值，即表格中最后一行最后一列的值
 value = table[n][m]
 return value

print("最大价值为：", str(dynamic(w, v, n, m, x)))
print("物品的索引：", x)

PS：python动态规划之背包问题

import numpy as np
def bag(weight,values,weight_cont):
 num = len(weight)
 weight.insert(0,0)
 values.insert(0,0)
 bag = np.zeros((num+1,weight_cont+1),dtype=np.int)
 for i in range(1,num+1):
  for j in range(1,weight_cont+1):
   if j >= weight[i]:
    bag[i][j] = max(bag[i-1][j],bag[i-1][j-weight[i]]+values[i])
   else:
    bag[i][j] = bag[i][j-1]
 return bag[-1][-1]
if __name__ == '__main__':
 weight = [1, 2, 4, 10, 12]
 values = [1200, 1500, 2000, 1300, 2500]
 weight_cont = 20
 re = bag(weight,values,weight_cont)
 print(re)

到此这篇关于python实现动态规划背包问题的文章就介绍到这了,更多相关python动态规划背包内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Python基于动态规划算法解决01背包问题实例

    Python基于动态规划算法解决01背包问题实例

    本文实例讲述了Python基于动态规划算法解决01背包问题.分享给大家供大家参考,具体如下: 在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决.n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来: 然后自底向上实现,代码如下: def bag(n,c,w,v): re

  • 浅析python实现动态规划背包问题

    一个包可以背4kg的东西,现在有四件东西,重量分别为1kg,4kg,3kg,1kg,价值为:1500,3000,2000,2000: 现在要求你,在包里背的东西价值最大,但是不能超过背包的最大载重量 #几件物品的重量 w = [0,1,4,3,1] #几件物品的价值 v= [0, 1500, 3000, 2000, 2000] #物品数量 n = len(w) - 1 #包的载重量 m = 4 #建立一个列表表示在包中的物品,元素是True时代表对应元素放入 x = [] #放入包中的总价值 v

  • 浅析Python中的for 循环

    Python for 和其他语言一样,也可以用来循环遍历对象,本文章向大家介绍Python for 循环的使用方法和实例,需要的朋友可与参考一下. 一个循环是一个结构,导致第一个程序要重复一定次数.重复不断循环的条件仍是如此.当条件变为假,循环结束和程序的控制传递给后面的语句循环. for循环: 在Python for循环遍历序列的任何物品,如一个列表或一个字符串,有能力. for循环语法是: for iterating_var in sequence: statements(s) 如果一个序列

  • 浅析Python 中整型对象存储的位置

    在 Python 整型对象所存储的位置是不同的, 有一些是一直存储在某个存储里面, 而其它的, 则在使用时开辟出空间. 说这句话的理由, 可以看看如下代码: a = 5 b = 5 a is b # True a = 500 b = 500 a is b # False 由上面的代码可知, 整型 5 是一直存在的, 而整型 500 不是一直存在的. 那么有哪些整数是一直存储的呢? a, b, c = 0, 0, 0 while a is b: i += 1 a, b = int(str(i)),

  • 浅析python中的分片与截断序列

    序列概念 在分片规则里list.tuple.str(字符串)都可以称为序列,都可以按规则进行切片操作 切片操作 注意切片的下标0代表顺序的第一个元素,-1代表倒序的第一个元素:且切片不包括右边界,例如[0:3]代表元素0.1.2不包括3. l=['a','b','c','d',5] 1.获取列表的前3个元素 >>> l[0:3] ['a', 'b', 'c'] >>> l[:3] ['a', 'b', 'c'] 2.获取列表的后3个元素 >>> l[-

  • 深入浅析python中的多进程、多线程、协程

    进程与线程的历史 我们都知道计算机是由硬件和软件组成的.硬件中的CPU是计算机的核心,它承担计算机的所有任务. 操作系统是运行在硬件之上的软件,是计算机的管理者,它负责资源的管理和分配.任务的调度. 程序是运行在系统上的具有某种功能的软件,比如说浏览器,音乐播放器等. 每次执行程序的时候,都会完成一定的功能,比如说浏览器帮我们打开网页,为了保证其独立性,就需要一个专门的管理和控制执行程序的数据结构--进程控制块. 进程就是一个程序在一个数据集上的一次动态执行过程. 进程一般由程序.数据集.进程控

  • Python基于动态规划算法计算单词距离

    本文实例讲述了Python基于动态规划算法计算单词距离.分享给大家供大家参考.具体如下: #!/usr/bin/env python #coding=utf-8 def word_distance(m,n): """compute the least steps number to convert m to n by insert , delete , replace . 动态规划算法,计算单词距离 >>> print word_distance("

  • 浅析python协程相关概念

    这篇文章是读者朋友的python协程的学习经验之谈,以下是全部内容: 协程的历史说来话长,要从生成器开始讲起. 如果你看过我之前的文章python奇遇记:迭代器和生成器 ,对生成器的概念应该很了解.生成器节省内存,用的时候才生成结果. # 生成器表达式 a = (x*x for x in range(10)) # next生成值 next(a()) # 输出0 next(a()) # 输出1 next(a()) # 输出4 与生成器产出数据不同的是,协程在产出数据的同时还可以接收数据,具体来说就

  • 浅析Python语言自带的数据结构有哪些

    Python作为一种脚本语言,其要求强制缩进,使其易读.美观,它的数据类型可以实现自动转换,而不需要像C.Java那样给变量定义数据类型,使其编写非常方便简单,所以广受大家的欢迎. 现如今,Python已经广泛的应用于数据分析.数据挖掘.机器学习等众多科学计算领域.所以既然涉及到科学计算,深入了解Python原生提供的数据结构是很有必要的,这样才能在数据的海洋中游刃有余.得心应手.本文便以此展开,做一个归纳整理,方便收藏. Python 一.序列结构 首先介绍的数据结构是序列结构,所谓序列,也就

  • 浅析Python+OpenCV使用摄像头追踪人脸面部血液变化实现脉搏评估

    使用摄像头追踪人脸由于血液流动引起的面部色素的微小变化实现实时脉搏评估. 效果如下(演示视频): 由于这是通过比较面部色素的变化评估脉搏所以光线.人体移动.不同角度.不同电脑摄像头等因素均会影响评估效果,实验原理是面部色素对比,识别效果存在一定误差,各位小伙伴且当娱乐,代码如下: import cv2 import numpy as np import dlib import time from scipy import signal # Constants WINDOW_TITLE = 'Pu

随机推荐