首页 > 编程知识 正文

python二维装箱问题(二维装箱问题算法)

时间:2023-12-24 12:05:31 阅读:320464 作者:CSPS

本文目录一览:

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的变量与对象是两个不同的概念,变量没有类型,类型存放在对象中,所以变量可以指向任意对象。列表只存储变量,当然不存在类型转换。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。