雙重背包問題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)