双重背包问题python

① 0/1背包问题python

看到这样贴code的就犯愁。。。看你的code还要自己格式化一遍，太折腾人了。。。

1、格式！

2、knapsack_dynamic 这个函数是哪里跳出来的? 和定义的函数不论名字还是参数个数，都对不上。

3、显示中文，至少要声明文件编码。比如要在脚本第一行声明

#encoding:utf-8

② 高分求python大神帮忙解答，实在有难度，做不出来

"""用itertools的组合工具combinations生成所有组合方案"""

importitertools

defsameSums(alst):
allsummary=sum(alst)
ifallsummary%2:
#数组总和不能被2整除既不可均分为等值的两部分
returnFalse
halfsum=allsummary/2#总和的半值为检测目标
forlinxrange(1,len(alst)/2+1):
#方案第一部分的数组长度从1位到数组半长
forsubinlist(itertools.combinations(alst,l)):
#按指定长度遍历组合方案
ifsum(sub)==halfsum:
#若当前方案的和为目标值则当前方案有效
#another为方案的第二部分数据列表
another=alst[:]
forxinsub:
another.pop(another.index(x))
printsub,tuple(another)
returnTrue
returnFalse


defoptsamesum(alst):
"""优化一下"""
allsummary=sum(alst)
ifallsummary%2:
returnFalse
halfsum=allsummary/2
ifmax(alst)>halfsum:
returnFalse
sortedlst=sorted(alst)[::-1]
forlinxrange(1,len(alst)/2+1):
forsubinlist(itertools.combinations(sortedlst,l)):
ifsum(sub)<halfsum:
break
ifsum(sub)==halfsum:
another=sortedlst[:]
forxinsub:
another.pop(another.index(x))
printlist(sub),another
returnTrue
returnFalse

if__name__=="__main__":
sameSums([4,7,6,3])
sameSums([3,3])
sameSums([4,12,16])
sameSums([5,1])

③ 请教我用python的贪心法做0/1背包问题

动态规划，可以给你说下思路。
我们用一个二维的矩阵A来存储中间结果，A[i][j]代表前i个物体装入容量为j的背包时可以得到的最优解，相当于是原问题的一个子问题，然后我们就可以写出递推式来更新这个矩阵，具体可以参考下详细的讲解，网上的博客非常多不用我再写一遍。

比如这种：http://zh.wikipedia.org/zh-cn/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98
先自己读一遍吧，有问题可以再问。

④ python急求简单作业给一个数组a找出是否有3个元素和为一个定值背包问题

#!/usr/bin/python
#encoding:utf-8

importitertools


defiter_result(alist,target):
formaybeinitertools.combinations(alist,3):
ifsum(maybe)==target:
yieldmaybe

a=[1,5,8,2,6,55,90]
forxiniter_result(a,103):
printx

先不必考虑背包问题的解法，这个问题就是简单地将所提供列表的任意三个元素抽取为子集--组合问题。python的itertools提供的combinations恰巧提供了这个功能。

⑤ Python动态背包问题，怎么解决

defbag(n,c,w,v):
res=[[-1forjinrange(c+1)]foriinrange(n+1)]
forjinrange(c+1):
res[0][j]=0
foriinrange(1,n+1):
forjinrange(1,c+1):
res[i][j]=res[i-1][j]
ifj>=w[i-1]andres[i][j]<res[i-1][j-w[i-1]]+v[i-1]:
res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
printres
returnres

defshow(n,c,w,res):
print'最大价值为:',res[n][c]
x=[Falseforiinrange(n)]
j=c
foriinrange(n,0,-1):
ifres[i][j]>res[i-1][j]:
x[i-1]=True
j-=w[i-1]
print('选择的物品为:')
foriinrange(n):
ifx[i]:
print'第',i,'个,'
print('')

if__name__=='__main__':
n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,7,6]
res=bag(n,c,w,v)
show(n,c,w,res)

• 输出：[[0,0,0,0,0,0,0,0,0,0,0],[-1,0,6,6,6,6,6,6,6,6,6],[-1,0,6,6,9,9,9,9,9,9,9],[-1,0,6,6,9,9,9,9,11,11,14],[-1,0,6,6,9,9,9,13,13,16,16],[-1,0,6,6,9,9,12,13,15,16,16]]

• 最大价值为:16

• 选择的物品为:

• 第0个,

• 第1个,

• 第3个,

⑥ Python中如何实现每循环一次,符号变一次

可以单独设置的。
问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业组合数学，计算复杂性理论密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下。
背包算法的一个早期应用是在测试的构建和评分中，测试者可以选择他们回答哪些问题。对于小例子来说，这是一个相当简单的过程，为测试者提供这样的选择。例如，如果考试包含12个问题，每个问题的价值为10分，测试者只需回答10个问题即可获得100分的最高分。

⑦ 求python用贪心算法实现01背包问题代码

numpy是科学计算用的。主要是那个array，比较节约内存，而且矩阵运算方便。成为python科学计算的利器。matplotlib是用于可视化的。只先学会XY的散点图，再加一个柱状图就可以了。其它的都可以暂时不学。几句话就成了。不用找本书。找个例子代码看完就会了。这两个只是计算用的。与机器学习有点儿关联。但还不是机器学习。 机器学习算法你可以使用R project，那个函数库更多些。 你要肯下功夫啃代码，最慢1小时就能掌握 numpy和matplotlib。如果你觉着难，总是想绕圈圈，想容易些，就很难弄会它。也许几天才会。

⑧ Python 如何将长度不同的字符串尽量均匀地分配到N个文件中每一行的字符串作为整体，不能打散。

背包问题的一个变种。或者说是一维装箱算法。

你将每一行字符串想象为一个物品，字符串的长度就是这个物品的大小。每个文件相当于不同的箱子，箱子的大小是固定的，装入的物品体积之和不能超过箱子的总容量。

问题就是：如何使用尽可能少的箱子来装入所有的物品，或者：如果使尽可能多的箱子空间利用率更高，以及类似的相关问题。

这类问题的答案不是一个简单的数字，它需要给出一个策略：物品1...n分别装入箱子1...m(m<=n).

对于二维装箱或三维等，区别主要在于解法的复杂度，但一个解法一般来说其思路是可以从一维扩展到二维或者三维的。

这类问题目前来说，没有全局最优解（即，没有一个算法能确保在所有情况下均能得到最好的结果），但可以得到局部最优解。算法有多种，如最常见的贪心算法，或动态规划。

贪心算法的思路比较简单：把所有的物品从大到小排好序，拿一个箱子，尝试装入最大的物品，如果不能装入，就尝试装入小一些的物品，如此循环，直到所有物品装入所有箱子。

算法很简单，但很多时候得到的结果并不理想。

⑨ 帮我看下这个程序有什么问题。。。。PYTHON中的背包问题，要求加起来20即可

你这个是背包问题吗？
维基网络上背包问题的定义是：
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
好像和你这里解决的不一样吧？
要不你在你程序要解决的问题描述一下？

⑩ 想问下大神python的背包问题的源代码(最好玩也有伪代码，请用递归法实现)，因为只学过递归法，所

递归有层数限制，所以最好不要用，能不用就不用，没有想到什么好的算法，弄了个简单粗暴的，包容量除以最小质量的，就是最多可以装多少个，然后全排列一遍三种商品，并计算价值，取最大的一个价值，代码如下：

a,b,c=2,2.5,3#三种商品质量
A,B,C=4,5,6#三种商品价值
m=100#包容量
ds=int(100/min(a,b,c))#最小质量取到最大数量

mx=0#最大价值
nl=[]#商品数量列表
fori1inrange(0,ds+1):#全排列
fori2inrange(0,ds+1-i1):
fori3inrange(0,ds+1-i1-i2):
#判断总质量超出则舍弃
n=i1*a+i2*b+i3*c
ifn>m:
continue
#计算总价值取最高值及排列并存储
j=i1*A+i2*B+i3*C
ifmx<j:
mx=j
nl=[i1,i2,i3]
#输出最大价值和组合
print(mx)
print(nl)