背包问题

标题

有一个背包能装10kg的物品，如今有6件物品分别为：

解决代码

#!/use/bin/env python 
 
# _*_ coding:utf-8 _*_ 
 
def knapsack(t, w): 
 
    """ 
 
    :param t: 背包总容量 
 
    :param w: 物品重量列表 
 
    :return: 
 
    """ 
 
    n = len(w)  # 可选的物品数量 
 
    stack = []  # 创建一个栈 
 
    k = 0  # 当前所选择的物品游标 
 
    while stack or k < n:  # 栈不为空或者k<n 
 
        while t > 0 and k < n:  # 还有残剩空间并且有物品可装 
 
            if t >= w[k]:  # 残剩空间大年夜于等于当前物品重量 
 
                stack.append(k)  # 把物品设备背包 
 
                t -= w[k]  # 背包空间削减 
 
            k += 1  # 持续向后找 
 
        if t == 0:  # 找到懂得 
 
            print(stack) 
 
        # 回退过程 
 
        k = stack.pop()  # 把最后一个物品拿出来 
 
        t += w[k]  # 背包总容量加上w[k] 
 
        k += 1  # 装入下一?物品 
 
knapsack(10, [1, 8, 4, 3, 5, 2]) 
 
""" 
 
[0, 2, 3, 5] 
 
[0, 2, 4] 
 
[1, 5] 
 
[3, 4, 5] 
 
"""  	
			
 6/7   首页 上一页 4 5 6 7 下一页 尾页
	
			

　　推荐阅读
　　“互联网+”让出租车更智慧
            
            走进淮北市运输治理处信息批示中间，一幅由6块液晶显示屏构成的监控屏幕映入眼帘，经由过程屏幕画面可以清楚地看到全市在运行出租车的及时地位和车内人员的音视频信息。批示中间以每周7日>>>详细阅读


本文标题：Python算法实战系列：栈
地址：http://www.17bianji.com/lsqh/35452.html
 1/2    1