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

2023-02-26 04:23:01Python010

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

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

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 = [] # 商品数量列表

for i1 in range(0, ds + 1): # 全排列

for i2 in range(0, ds + 1 - i1):

for i3 in range(0, ds + 1 - i1 - i2):

# 判断总质量超出则舍弃

n = i1 * a + i2 * b + i3 * c

if n > m:

continue

# 计算总价值取最高值及排列并存储

j = i1 * A + i2 * B + i3 * C

if mx < j:

mx = j

nl = [i1, i2, i3]

# 输出最大价值和组合

print(mx)

print(nl)

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

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

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

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

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

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

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

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

贪心算法

动态规划的思路是，每装入一个物品到箱子里,就提出一个新的问题:【以所有未装入的物品和这个箱子剩余空间作为条件，怎么装？】而这样的问题随着装入的物品不同，会有许多个，选择其中最终剩余空间最小的方式，就是局部最优的解。一般来说，这比较适合用递归来处理，但它的复杂度是远远高于贪心算法的。

动态规划

当然，还有其它的算法，不同的算法有不同的思路，复杂度也不同，适用范围也有一些区别。所以，没必要纠结于【最好】，只要【尽可能好】。

否则的话，关于装箱问题，都可以出许多篇博士论文了。

针对题主这一问题，贪心算法的解决思路就是读入每一行，然后排序，从大到小装入剩余空间最大的箱子（即装入内容最少的箱子）。

可以参考以下处理方式：

1.Python数据结构篇

数据结构篇主要是阅读[Problem Solving with Python](Welcome to Problem Solving with Algorithms and Data Structures) [该网址链接可能会比较慢]时写下的阅读记录，当然，也结合了部分[算法导论](Introduction 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免费下载原书电子版**]之后写下的读书总结，原书大部分内容结合了经典书籍[算法导论](Introduction 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 Introduction](Python Algorithms)

本节主要是对原书中的内容做些简单介绍，说明算法的重要性以及各章节的内容概要。

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

**本节主要介绍了三个内容：算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。**