问题描述:01背包是在N件物品取出若干件放在空间为V的背包里,每件物品的体积为V1,V2……Vn,与之相对应的价值为P1,P2……Pn(所有的体积值均为整数)。
环境工具:win7 python2.7
解决过程:考虑用动态规划的方法来解决
阶段 【在前N件物品中,选取若干件物品放入背包中】
状态 【在前N件物品中,选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值】
决策 【第N件物品放或者不放】
可以写出动态转移方程
用f[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值
f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]}
基本上所有跟背包相关的问题的方程都是由它衍生出来的。
演变解释@考虑在V的空间下,放入N件物品能获得最大价值(前N-1物品是最大价值的,第N件产品可以放进去)
=》考虑在V - Vn的空间下,放入N-1件物品能获得最大价值(前N-2物品是最大价值的,第N-1件物品可以放进去)
=》考虑在V - Vn-1 - Vn的空间下,放入N-2件物品能获得最大价值(前N-3物品是最大价值的,第N-2件物品可以放进去)
......
=》考虑在V - V3 - V4... - Vn的空间下,放入2件物品能获得最大价值(前1物品是最大价值的,第2件物品可以放进去)
=》考虑在V - V2 - V3 - V4... - Vn的空间下,放入1件物品能获得最大价值(前0物品的价值是0,第1件物品可以放进去)
源代码如下
#! C:\\Python27\\python.exe
# -*- coding:utf-8 -*-
import copy
class DynamicBag:
def __init__(self, limitVolume, itemsVolume, itemsValue):
self.limitVolume = limitVolume #最大体积上限,容积
self.itemsVolume = itemsVolume #所有项的每项的体积
self.itemsValue = itemsValue #所有项的每项的价值
self.resultSumVolume = 0 #最大价值的占用体积
self.resultSumValue = 0 #最大价值
self.resultItemsVolume = [] #最大价值的每项体积
self.resultItemsValue = [] #最大价值的每项价值
def dynamicSuitResult(self):
itemsCount = len(self.itemsVolume)
if itemsCount == len(self.itemsValue):
allItems = [] #所有项的下标
self.itemsVolume.append(0) #添加0项,方便计算
self.itemsValue.append(0)
itemsCount = itemsCount + 1
for k in range(itemsCount):
allItems.append(k)
(self.resultSumVolume, self.resultSumValue, resulItems) = self.dynamic01Bag(allItems[itemsCount-1], limitVolume, allItems)#获得最大价值的占用体积,最大价值,组成项的索引
del resulItems[resulItems.index(itemsCount-1)]#去除0项索引
for k in resulItems:
self.resultItemsVolume.append(self.itemsVolume[k])#根据最大价值的组成项的索引获得项
self.resultItemsValue.append(self.itemsValue[k])
else:
print("args error!")
return (self.resultSumVolume, self.resultSumValue, self.resultItemsVolume, self.resultItemsValue)#返回 最大价值的占用体积,最大价值,最大价值的每项体积,最大价值的每项价值
def dynamic01Bag(self, oneItem, limitVolume, allItems):
suitSumVolume = 0 #当前项的最大价值占用体积
suitSumValue = 0 #当前项的当前最大价值
suitItems = [] #当前项的当前最大价值的组成项的索引
partItems = copy.copy(allItems)
del partItems[partItems.index(oneItem)]#去掉当前项
if len(partItems)==1:#前一项只有一项
if limitVolume < self.itemsVolume[partItems[0]]:#容积小于前一项
return (suitSumVolume, suitSumValue, suitItems)
elif limitVolume >= (self.itemsVolume[partItems[0]] + self.itemsVolume[oneItem]):#容积大于等于前一项+当前项
suitSumVolume = self.itemsVolume[partItems[0]] + self.itemsVolume[oneItem]
suitSumValue = self.itemsValue[partItems[0]] + self.itemsValue[oneItem]
suitItems.append(oneItem)
suitItems.append(partItems[0])
return (suitSumVolume, suitSumValue, suitItems)
else:#容积大于等于前一项,小于前一项+当前项
suitSumVolume = self.itemsVolume[partItems[0]]
suitSumValue = self.itemsValue[partItems[0]]
suitItems.append(partItems[0])
return (suitSumVolume, suitSumValue, suitItems)
else:#前一项有多项
suitVolume1 = 0
suitValue1 = 0
suitVolume2 = 0
suitValue2 = 0
suitIndex1 = 0
suitIndex2 = 0
result = []
for k in range(len(partItems)):
(aSumVolume, bSumValue, cItems)=self.dynamic01Bag(partItems[k], limitVolume - self.itemsVolume[oneItem], partItems)#对多个前一项的每项求最大值
result.append((aSumVolume, bSumValue, cItems))
if (aSumVolume + self.itemsVolume[oneItem]) <= limitVolume:#存在容积大于等于前一项+当前项的情况,获取最大的前一项+当前项
if (bSumValue + self.itemsValue[oneItem]) > suitValue1:#对多个前一项的最大值,求最优
suitVolume1 = aSumVolume + self.itemsVolume[oneItem]
suitValue1 = bSumValue + self.itemsValue[oneItem]
suitIndex1 = k
if bSumValue > suitValue2:#容积小于所有的前一项+当前项情况下使用,获取最大的前一项
suitVolume2 = aSumVolume
suitValue2 = bSumValue
suitIndex2 = k
if suitValue1 > 0:#存在容积大于等于前一项+当前项的情况,获取最大的前一项+当前项
suitSumVolume = suitVolume1
suitSumValue = suitValue1
suitItems.append(oneItem)
suitItems.extend(result[suitIndex1][2])
return (suitSumVolume, suitSumValue, suitItems)
else:#容积小于所有的前一项+当前项情况下使用,获取最大的前一项
suitSumVolume = suitVolume2
suitSumValue = suitValue2
suitItems.extend(result[suitIndex2][2])
return (suitSumVolume, suitSumValue, suitItems)
#算法验证
if __name__ == '__main__':
limitVolume = 20#体积上限
itemsVolume = [1,2,5,7,9]#单个总体积
itemsValue = [1,1,1,2,2]#单个总价值
hk01bag = DynamicBag(limitVolume, itemsVolume, itemsValue)
(resultSumVolume, resultSumValue, resultItemsVolume, resultItemsValue) = hk01bag.dynamicSuitResult()
print '最大价值:'+str(resultSumValue)
print '最大价值的单个价值:'
print resultItemsValue
print '最大价值的总体积:'+str(resultSumVolume)
print '最大价值的单个总体积:'
print resultItemsVolume
相关推荐
我用Python写的一些算法 #算法 ##排序算法:sort文件夹下面 冒泡排序 插入排序 归并排序 快速排序 随机快速排序 选择排序 堆排序 计数排序 ##查找算法 二分查找算法 第k小数选择算法 随机第k小数选择算法 计算...
2.领域:智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真,更多内容可点击博主头像 3.内容:标题所示,对于介绍可点击主页搜索博客 4.适合人群:本科,硕士...
然后,为快速有效地求解0-1背包问题,引入贪心修复与优化策略处理非正常编码个体,得到基于混沌理论的二进制乌鸦算法(chaotic binary crow search algorithm,CBCSA)。仿真实验表明,CBCSA具有良好的全局寻优能力...
自己实现后面的实例算法(比如:0-1背包问题) 1.如何玩算法? 1.1 学习要点 玩算法需要做到三点: 【第一点】 对遇到的特殊问题能够自己设计出算法实现(可以是智力游戏题目或者工作中的实际问题等) 【第二点】 对原理...
安装 # (Optional) add user to serial groupsudo usermod -a -G tty pi# Logout and login again# Common dependenciessudo apt-get updatesudo apt-get upgradesudo apt-get install git libjpeg-dev python-pip ...
有关该问题的更多信息:使用DEAP库解决人工智能主题的Python背包问题学生:Amadeu Martim Silva De Oliveira 注册: 1191114977 项目状态:已完成该算法的操作说明: 1.要正确运行算法,只需下载文件夹problemMbag中...
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
图与散列表:图实验+散列表实验 贪心算法:背包问题+哈夫曼编码问题+动态规划 分治算法:求连续子数组的最大和+矩阵乘法的srtassen算法 SQL数据库:数据库的建立、查询等基础操作
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
前端技术: ... CSS :用于设计网页外观和样式的样式表语言。 JavaScript:用于在网页上...Python:一种多用途编程语言,在Web开发中常用。 Ruby on Rails:一个基于Ruby编程语言的Web应用框架,提供了高效的开发工具。
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
1.5.1 背包问题 1.5.2 物流选址 1.5.4 货位优化 ##### 1.6 电力系统优化研究 1.6.1 微电网优化 1.6.2 配电网系统优化 1.6.3 配电网重构 1.6.4 有序充电 1.6.5 储能双层优化调度 1.6.6 储能优化配置 ### 2 ...
尖叫背包概述用于处理远程和本地数据资源同步的实用程序。 开发用于 CheckM 但希望足够通用以用于其他地方。安装应该很简单 pip install ScreamingBackpack示例用法该实用程序的工作原理是在数据目录中放置一个小...