背包問題python

Ⅰ 請教我用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用貪心演算法實現01背包問題代碼

numpy是科學計算用的。主要是那個array，比較節約內存，而且矩陣運算方便。成為python科學計算的利器。matplotlib是用於可視化的。只先學會XY的散點圖，再加一個柱狀圖就可以了。其它的都可以暫時不學。幾句話就成了。不用找本書。找個例子代碼看完就會了。這兩個只是計算用的。與機器學習有點兒關聯。但還不是機器學習。 機器學習演算法你可以使用R project，那個函數庫更多些。 你要肯下功夫啃代碼，最慢1小時就能掌握 numpy和matplotlib。如果你覺著難，總是想繞圈圈，想容易些，就很難弄會它。也許幾天才會。

Ⅲ 幫我看下這個程序有什麼問題。。。。PYTHON中的背包問題，要求加起來20即可

你這個是背包問題嗎？
維基網路上背包問題的定義是：
背包問題(Knapsack problem)是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。
好像和你這里解決的不一樣吧？
要不你在你程序要解決的問題描述一下？

Ⅳ 0/1背包問題python

看到這樣貼code的就犯愁。。。看你的code還要自己格式化一遍，太折騰人了。。。

1、格式！

2、knapsack_dynamic 這個函數是哪裡跳出來的? 和定義的函數不論名字還是參數個數，都對不上。

3、顯示中文，至少要聲明文件編碼。比如要在腳本第一行聲明

#encoding:utf-8

Ⅳ 想問下大神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)

Ⅵ 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中的數據結構分析

1.Python數據結構篇

數據結構篇主要是閱讀[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [該網址鏈接可能會比較慢]時寫下的閱讀記錄，當然，也結合了部分[演算法導論](Introction to Algorithms)
中的內容，此外還有不少wikipedia上的內容，所以內容比較多，可能有點雜亂。這部分主要是介紹了如何使用Python實現常用的一些數據結構，例
如堆棧、隊列、二叉樹等等，也有Python內置的數據結構性能的分析，同時還包括了搜索和排序(在演算法設計篇中會有更加詳細的介紹)的簡單總結。每篇文
章都有實現代碼，內容比較多，簡單演算法一般是大致介紹下思想及演算法流程，復雜的演算法會給出各種圖示和代碼實現詳細介紹。

**這一部分是下
面演算法設計篇的前篇，如果數據結構還不錯的可以直接看演算法設計篇，遇到問題可以回來看數據結構篇中的某個具體內容充電一下，我個人認為直接讀演算法設計篇比
較好，因為大家時間也都比較寶貴，如果你會來讀這些文章說明你肯定有一定基礎了，後面的演算法設計篇中更多的是思想，這里更多的是代碼而已，嘿嘿。**

(1)[搜索](Python Data Structures)

簡述順序查找和二分查找，詳述Hash查找(hash函數的設計以及如何避免沖突)

(2)[排序](Python Data Structures)

簡述各種排序演算法的思想以及它的圖示和實現

(3)[數據結構](Python Data Structures)

簡述Python內置數據結構的性能分析和實現常用的數據結構：棧、隊列和二叉堆

(4)[樹總結](Python Data Structures)

簡述二叉樹，詳述二叉搜索樹和AVL樹的思想和實現

2.Python演算法設計篇

演算法設計篇主要是閱讀[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**點擊鏈接可進入Springer免費下載原書電子版**]之後寫下的讀書總結，原書大部分內容結合了經典書籍[演算法導論](Introction to Algorithms)，
內容更加細致深入，主要是介紹了各種常用的演算法設計思想，以及如何使用Python高效巧妙地實現這些演算法，這里有別於前面的數據結構篇，部分演算法例如排
序就不會詳細介紹它的實現細節，而是側重於它內在的演算法思想。這部分使用了一些與數據結構有關的第三方模塊，因為這篇的重點是演算法的思想以及實現，所以並
沒有去重新實現每個數據結構，但是在介紹演算法的同時會分析Python內置數據結構以及第三方數據結構模塊的優缺點，也就意味著該篇比前面都要難不少，但
是我想我的介紹應該還算簡單明了，因為我用的都是比較朴實的語言，並沒有像演算法導論一樣列出一堆性質和定理，主要是對著某個問題一步步思考然後演算法就出來
了，嘿嘿，除此之外，裡面還有很多關於python開發的內容，精彩真的不容錯過！

這里每篇文章都有實現代碼，但是代碼我一般都不會分
析，更多地是分析演算法思想，所以內容都比較多，即便如此也沒有包括原書對應章節的所有內容，因為內容實在太豐富了，所以我只是選擇經典的演算法實例來介紹算
法核心思想，除此之外，還有不少內容是原書沒有的，部分是來自演算法導論，部分是來自我自己的感悟，嘻嘻。該篇對於大神們來說是小菜，請一笑而過，對於菜鳥
們來說可能有點難啃，所以最適合的是和我水平差不多的，對各個演算法都有所了解但是理解還不算深刻的半桶水的程序猿，嘿嘿。

本篇的順序按照原書[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章節來安排的(章節標題部分相同部分不同喲)，為了節省時間以及保持原著的原滋原味，部分內容(一般是比較難以翻譯和理解的內容)直接摘自原著英文內容。

**1.
你也許覺得很多內容你都知道嘛，沒有看的必要，其實如果是我的話我也會這么想，但是如果只是歸納一個演算法有哪些步驟，那這個總結也就沒有意義了，我覺得這
個總結的亮點在於想辦法說清楚一個演算法是怎麼想出來的，有哪些需要注意的，如何進行優化的等等，採用問答式的方式讓讀者和我一起來想出某個問題的解，每篇
文章之後都還有一兩道小題練手喲**

**2.你也許還會說演算法導論不是既權威又全面么，基本上每個演算法都還有詳細的證明呢，讀演算法導論豈
不更好些，當然，你如果想讀演算法導論的話我不攔著你，讀完了感覺自己整個人都不好了別怪小弟沒有提醒你喲，嘻嘻嘻，左一個性質右一個定理實在不適合演算法科
普的啦，沒有多少人能夠堅持讀完的。但是碼農與蛇的故事內容不多喲，呵呵呵**

**3.如果你細讀本系列的話我保證你會有不少收獲的，需要看演算法導論哪個部分的地方我會給出提示的，嘿嘿。溫馨提示，前面三節內容都是介紹基礎知識，所以精彩內容從第4節開始喲，么么噠 O(∩_∩)O~**

(1)[Python Algorithms - C1 Introction](Python Algorithms)

本節主要是對原書中的內容做些簡單介紹，說明演算法的重要性以及各章節的內容概要。

(2)[Python Algorithms - C2 The basics](Python Algorithms)

**本節主要介紹了三個內容：演算法漸近運行時間的表示方法、六條演算法性能評估的經驗以及Python中樹和圖的實現方式。**

(3)[Python Algorithms - C3 Counting 101](Python Algorithms)

原書主要介紹了一些基礎數學，例如排列組合以及遞歸循環等，但是本節只重點介紹計算演算法的運行時間的三種方法

(4)[Python Algorithms - C4 Inction and Recursion and Rection](Python Algorithms)

**本節主要介紹演算法設計的三個核心知識：Inction(推導)、Recursion(遞歸)和Rection(規約)，這是原書的重點和難點部分**

(5)[Python Algorithms - C5 Traversal](Python Algorithms)

**本節主要介紹圖的遍歷演算法BFS和DFS，以及對拓撲排序的另一種解法和尋找圖的(強)連通分量的演算法**

(6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms)

**本節主要介紹分治法策略，提到了樹形問題的平衡性以及基於分治策略的排序演算法**

(7)[Python Algorithms - C7 Greedy](Python Algorithms)

**本節主要通過幾個例子來介紹貪心策略，主要包括背包問題、哈夫曼編碼和最小生成樹等等**

(8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms)

**本節主要結合一些經典的動規問題介紹動態規劃的備忘錄法和迭代法這兩種實現方式，並對這兩種方式進行對比**

(9)[Python Algorithms - C9 Graphs](Python Algorithms)

**本節主要介紹圖演算法中的各種最短路徑演算法，從不同的角度揭示它們的內核以及它們的異同**

Ⅷ Python 如何將長度不同的字元串盡量均勻地分配到N個文件中每一行的字元串作為整體，不能打散。

背包問題的一個變種。或者說是一維裝箱演算法。

你將每一行字元串想像為一個物品，字元串的長度就是這個物品的大小。每個文件相當於不同的箱子，箱子的大小是固定的，裝入的物品體積之和不能超過箱子的總容量。

問題就是：如何使用盡可能少的箱子來裝入所有的物品，或者：如果使盡可能多的箱子空間利用率更高，以及類似的相關問題。

這類問題的答案不是一個簡單的數字，它需要給出一個策略：物品1...n分別裝入箱子1...m(m<=n).

對於二維裝箱或三維等，區別主要在於解法的復雜度，但一個解法一般來說其思路是可以從一維擴展到二維或者三維的。

這類問題目前來說，沒有全局最優解（即，沒有一個演算法能確保在所有情況下均能得到最好的結果），但可以得到局部最優解。演算法有多種，如最常見的貪心演算法，或動態規劃。

貪心演算法的思路比較簡單：把所有的物品從大到小排好序，拿一個箱子，嘗試裝入最大的物品，如果不能裝入，就嘗試裝入小一些的物品，如此循環，直到所有物品裝入所有箱子。

演算法很簡單，但很多時候得到的結果並不理想。

Ⅸ 有哪些用 Python 語言講演算法和數據結構的書

1.Python數據結構篇
數據結構篇主要是閱讀[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [該網址鏈接可能會比較慢]時寫下的閱讀記錄，當然，也結合了部分[演算法導論](Introction to Algorithms)中的內容，此外還有不少wikipedia上的內容，所以內容比較多，可能有點雜亂。這部分主要是介紹了如何使用Python實現常用的一些數據結構，例如堆棧、隊列、二叉樹等等，也有Python內置的數據結構性能的分析，同時還包括了搜索和排序(在演算法設計篇中會有更加詳細的介紹)的簡單總結。每篇文章都有實現代碼，內容比較多，簡單演算法一般是大致介紹下思想及演算法流程，復雜的演算法會給出各種圖示和代碼實現詳細介紹。
**這一部分是下面演算法設計篇的前篇，如果數據結構還不錯的可以直接看演算法設計篇，遇到問題可以回來看數據結構篇中的某個具體內容充電一下，我個人認為直接讀演算法設計篇比較好，因為大家時間也都比較寶貴，如果你會來讀這些文章說明你肯定有一定基礎了，後面的演算法設計篇中更多的是思想，這里更多的是代碼而已，嘿嘿。**
(1)[搜索](Python Data Structures)
簡述順序查找和二分查找，詳述Hash查找(hash函數的設計以及如何避免沖突)
(2)[排序](Python Data Structures)
簡述各種排序演算法的思想以及它的圖示和實現
(3)[數據結構](Python Data Structures)
簡述Python內置數據結構的性能分析和實現常用的數據結構：棧、隊列和二叉堆
(4)[樹總結](Python Data Structures)
簡述二叉樹，詳述二叉搜索樹和AVL樹的思想和實現
2.Python演算法設計篇
演算法設計篇主要是閱讀[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)[**點擊鏈接可進入Springer免費下載原書電子版**]之後寫下的讀書總結，原書大部分內容結合了經典書籍[演算法導論](Introction to Algorithms)，內容更加細致深入，主要是介紹了各種常用的演算法設計思想，以及如何使用Python高效巧妙地實現這些演算法，這里有別於前面的數據結構篇，部分演算法例如排序就不會詳細介紹它的實現細節，而是側重於它內在的演算法思想。這部分使用了一些與數據結構有關的第三方模塊，因為這篇的重點是演算法的思想以及實現，所以並沒有去重新實現每個數據結構，但是在介紹演算法的同時會分析Python內置數據結構以及第三方數據結構模塊的優缺點，也就意味著該篇比前面都要難不少，但是我想我的介紹應該還算簡單明了，因為我用的都是比較朴實的語言，並沒有像演算法導論一樣列出一堆性質和定理，主要是對著某個問題一步步思考然後演算法就出來了，嘿嘿，除此之外，裡面還有很多關於python開發的內容，精彩真的不容錯過！
這里每篇文章都有實現代碼，但是代碼我一般都不會分析，更多地是分析演算法思想，所以內容都比較多，即便如此也沒有包括原書對應章節的所有內容，因為內容實在太豐富了，所以我只是選擇經典的演算法實例來介紹演算法核心思想，除此之外，還有不少內容是原書沒有的，部分是來自演算法導論，部分是來自我自己的感悟，嘻嘻。該篇對於大神們來說是小菜，請一笑而過，對於菜鳥們來說可能有點難啃，所以最適合的是和我水平差不多的，對各個演算法都有所了解但是理解還不算深刻的半桶水的程序猿，嘿嘿。
本篇的順序按照原書[Python Algorithms: Mastering Basic Algorithms in the Python Language](Python Algorithms: Mastering Basic Algorithms in the Python Language)的章節來安排的(章節標題部分相同部分不同喲)，為了節省時間以及保持原著的原滋原味，部分內容(一般是比較難以翻譯和理解的內容)直接摘自原著英文內容。
**1.你也許覺得很多內容你都知道嘛，沒有看的必要，其實如果是我的話我也會這么想，但是如果只是歸納一個演算法有哪些步驟，那這個總結也就沒有意義了，我覺得這個總結的亮點在於想辦法說清楚一個演算法是怎麼想出來的，有哪些需要注意的，如何進行優化的等等，採用問答式的方式讓讀者和我一起來想出某個問題的解，每篇文章之後都還有一兩道小題練手喲**
**2.你也許還會說演算法導論不是既權威又全面么，基本上每個演算法都還有詳細的證明呢，讀演算法導論豈不更好些，當然，你如果想讀演算法導論的話我不攔著你，讀完了感覺自己整個人都不好了別怪小弟沒有提醒你喲，嘻嘻嘻，左一個性質右一個定理實在不適合演算法科普的啦，沒有多少人能夠堅持讀完的。但是碼農與蛇的故事內容不多喲，呵呵呵**
**3.如果你細讀本系列的話我保證你會有不少收獲的，需要看演算法導論哪個部分的地方我會給出提示的，嘿嘿。溫馨提示，前面三節內容都是介紹基礎知識，所以精彩內容從第4節開始喲，么么噠 O(∩_∩)O~**
(1)[Python Algorithms - C1 Introction](Python Algorithms)
本節主要是對原書中的內容做些簡單介紹，說明演算法的重要性以及各章節的內容概要。
(2)[Python Algorithms - C2 The basics](Python Algorithms)
**本節主要介紹了三個內容：演算法漸近運行時間的表示方法、六條演算法性能評估的經驗以及Python中樹和圖的實現方式。**
(3)[Python Algorithms - C3 Counting 101](Python Algorithms)
原書主要介紹了一些基礎數學，例如排列組合以及遞歸循環等，但是本節只重點介紹計算演算法的運行時間的三種方法
(4)[Python Algorithms - C4 Inction and Recursion and Rection](Python Algorithms)
**本節主要介紹演算法設計的三個核心知識：Inction(推導)、Recursion(遞歸)和Rection(規約)，這是原書的重點和難點部分**
(5)[Python Algorithms - C5 Traversal](Python Algorithms)
**本節主要介紹圖的遍歷演算法BFS和DFS，以及對拓撲排序的另一種解法和尋找圖的(強)連通分量的演算法**
(6)[Python Algorithms - C6 Divide and Combine and Conquer](Python Algorithms)
**本節主要介紹分治法策略，提到了樹形問題的平衡性以及基於分治策略的排序演算法**
(7)[Python Algorithms - C7 Greedy](Python Algorithms)
**本節主要通過幾個例子來介紹貪心策略，主要包括背包問題、哈夫曼編碼和最小生成樹等等**
(8)[Python Algorithms - C8 Dynamic Programming](Python Algorithms)
**本節主要結合一些經典的動規問題介紹動態規劃的備忘錄法和迭代法這兩種實現方式，並對這兩種方式進行對比**
(9)[Python Algorithms - C9 Graphs](Python Algorithms)

Ⅹ 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恰巧提供了這個功能。