python二維裝箱問題（二維裝箱問題演算法）

本文目錄一覽：

• 1、Python 如何將長度不同的字元串盡量均勻地分配到N個文件中？每一行的字元串作為整體，不能打散。
• 2、一些Python中的二維數組的操作方法
• 3、python基礎題（選擇排序、二維列表）如何做，急求
• 4、python的二維list問題
• 5、python 列表 是否存在裝箱和拆箱問題？

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

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

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

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

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

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

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

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

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

貪心演算法

動態規劃的思路是，每裝入一個物品到箱子里,就提出一個新的問題:【以所有未裝入的物品和這個箱子剩餘空間作為條件，怎麼裝？】而這樣的問題隨著裝入的物品不同，會有許多個，選擇其中最終剩餘空間最小的方式，就是局部最優的解。一般來說，這比較適合用遞歸來處理，但它的複雜度是遠遠高於貪心演算法的。

動態規劃

當然，還有其它的演算法，不同的演算法有不同的思路，複雜度也不同，適用範圍也有一些區別。所以，沒必要糾結於【最好】，只要【儘可能好】。

否則的話，關於裝箱問題，都可以出許多篇博士論文了。

針對題主這一問題，貪心演算法的解決思路就是讀入每一行，然後排序，從大到小裝入剩餘空間最大的箱子（即裝入內容最少的箱子）。

可以參考以下處理方式：

一些Python中的二維數組的操作方法

一些Python中的二維數組的操作方法

這篇文章主要介紹了一些Python中的二維數組的操作方法,是Python學習當中的基礎知識,需要的朋友可以參考下

需要在程序中使用二維數組，網上找到一種這樣的用法：

#創建一個寬度為3，高度為4的數組

#[[0,0,0],

# [0,0,0],

# [0,0,0],

# [0,0,0]]

myList = [[0] * 3] * 4

但是當操作myList[0][1] = 1時，發現整個第二列都被賦值，變成

[[0,1,0],

[0,1,0],

[0,1,0],

[0,1,0]]

為什麼…一時搞不懂,後面翻閱The Python Standard Library 找到答案

list * n—n shallow copies of list concatenated, n個list的淺拷貝的連接

例:

lists = [[]] * 3

lists

[[], [], []]

lists[0].append(3)

lists

[[3], [3], [3]]

[[]]是一個含有一個空列表元素的列表,所以[[]]*3表示3個指向這個空列表元素的引用,修改任何

一個元素都會改變整個列表:

所以需要用另外一種方式進行創建多維數組,以免淺拷貝:

lists = [[] for i in range(3)]

lists[0].append(3)

lists[1].append(5)

lists[2].append(7)

lists

[[3], [5], [7]]

之前的二維數組創建方式為:

myList = [([0] * 3) for i in range(4)]

python基礎題（選擇排序、二維列表）如何做，急求

from random import sample

data=sample(range(1,101),30)

arr=[data[x:x+6] for x in range(0,len(data),6)]

print(‘轉變為5*6的二維列表’,arr,’\n’)

print(‘該二維列表每行最大值：’,list(map(max,arr)),’\n’)

print(‘該二維列表每行最小值：’,list(map(min,arr)),’\n’)

print(‘該二維列表每行平均值：’,list(map(lambda x:sum(x)/len(x),arr)),’\n’)

print(‘大於平均值個數：’,list(map(lambda x:len([y for y in x if ysum(x)/len(x)]),arr)),’\n’)

print(‘小於平均值個數：’,list(map(lambda x:len([y for y in x if ysum(x)/len(x)]),arr)))

python的二維list問題

list 的 乘法是將裡面的對象複製了一遍，並沒有創建新的對象(object)。比方說

b = [1, 2, 3]

b 是一個 list 對象，如果

a = [b]*3

那麼a就是一個包含三個 b 的列表，這個列表中的每一個對象都是b，所以你修改任意一個對象，實際都是在修改 b本身。用 id() 可以查看對象id，你可以發現a中的每一個元素都是同一個id

 b = [0, 0, 0]

 id(b)

47599855534232

 a = [b]*3

 a

[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

 id(a)

47599860614424

 id(a[0])

47599855534232

 id(a[1])

47599855534232

 id(a[2])

47599855534232

 id(a[2]) == id(b)

True

如果你想a中每一個元素都是不同的對象，可以用下面的代碼：

a = [[0]*3 for i in range(3)]

python 列表 是否存在裝箱和拆箱問題？

裝箱拆箱是指其他語言中值和對象之間的自動轉換，python不存在在這個問題，一切皆對象。python的變數與對象是兩個不同的概念，變數沒有類型，類型存放在對象中，所以變數可以指向任意對象。列表只存儲變數，當然不存在類型轉換。