背包问题

发表于   |   分类于

栈的应用其二：背包问题

处理逻辑

  1. knap(weight,n)表示n件物品的重量
    • 若不选最后一件物品(重量为W(n-1))，knap(weight,n-1)的解即为knap(weight,n)的解
    • 若选择最后一件物品，若knap(weight-W(n-1),n-1)有解，其解加上最后一件物品就是kanp(weight,n)的解，即前者有解后者也有解

  2. 递归的考虑问题，n件物品的背包问题可归结为两个n-1件物品的背包问题：

    • 同样重量，物品数量减一
    • 减少重量，物品数量减一

  3. 几种最简单的情况

重量 解情况
等于0 有解
小于0 无解
大于0且无物品可用 无解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env python
#_*_ coding:utf-8 _*_
def knap_rec(weight,wlist,n):
    if weight == 0:
        return True
    if weight < 0 or (weight >1 and n<1):
        return False
    if knap_rec(weight - wlist[n-1], wlist, n - 1):
        print 'Item' + str(n) + ':',wlist[n - 1]
        return True
    if knap_rec(weight, wlist, n-1):
        return True
    else:return False
wlist = [1,2,3,4,5,]
n = len(wlist)
weight = 10
knap_rec(weight,wlist,n)
  • 程序出自 《数据结构与算法Python语言描述》