动态规划解决背包问题

《算法图解》动态规划解决背包问题笔记

问题描述

假设你要去野营。你有一个容量为6磅的背包，需要决定该携带下面的哪些东西。其中每样东西都有相应的价值，价值越大意味着越重要：

• 水（重3磅，价值10）

• 书（重1磅，价值3）

• 食物（重2磅，价值9）

• 夹克（重2磅，价值5）

• 相机（重1磅，价值6）

请问携带哪些东西时价值最高？

代码

class Goods:

    def __init__(self, name, weight, price):
        self.name = name
        self.weight = weight
        self.price = price


class Cell:
    def __init__(self, good_list, total_price, total_weight):
        self.good_list = good_list
        self.total_price = total_price
        self.total_weight = total_weight

    def __str__(self):
        return str(self.total_price) + ',' + str(self.total_weight)

from g import Goods, Cell

backpack = 6

goodList = [
    Goods('water', 3, 10),
    Goods('book', 1, 3),
    Goods('food', 2, 9),
    Goods('jacket', 2, 5),
    Goods('camera', 1, 6)
]

table = []

for i, good in enumerate(goodList):
    childTable = []
    for j in range(1, backpack + 1):
        # 表格为空，没有参照行可以直接添加，只要背包能放下
        if len(table) == 0:
            if j >= good.weight:
                # 当商品重量能放下，记录商品信息
                childTable.append(Cell([good.name], good.price, good.weight))
            else:
                # 背包放不下，初始化站位信息
                childTable.append(Cell([], 0, 0))
        else:
            # 上一行，同列表格中的信息
            last_cell = table[i - 1][j - 1]
            # 背包还有剩余空间
            if j - good.weight > 0:
                # 获取上一行剩余空间的信息
                last_same_weight_cell = table[i - 1][j - good.weight - 1]
                current = good.price + last_same_weight_cell.total_price
                # 如果剩余空间的加上当前商品的大于上一行同列信息
                if current > last_cell.total_price:

                    temp_good_list = last_same_weight_cell.good_list.copy()
                    temp_good_list.append(good.name)

                    cell_total_price = last_same_weight_cell.total_price + good.price
                    cell_total_weight = last_same_weight_cell.total_weight + good.weight

                    childTable.append(Cell(temp_good_list,cell_total_price,cell_total_weight))
                else:
                    childTable.append(Cell(last_cell.good_list,last_cell.total_price,last_cell.total_weight))
            else:
                if good.price > last_cell.total_price and good.weight == j:
                    childTable.append(Cell([good.name], good.price, good.weight))
                else:
                    childTable.append(Cell(last_cell.good_list, last_cell.total_price, last_cell.total_weight))


    table.append(childTable)


for childTable in table:
    for c in childTable:
        out_str = str(c.total_price) + '(' + str(c.good_list) + ')'
        print(out_str,end='\t')
    print()

思路

构建一个表格，表格的行是以背包最小单位进行划分的，比如背包是3.5，那么就是0.5,1,1.5,2,2.5,3,3.5，列就是不同的物品，构建出表格后，按照列的大小，向表格里面放物品。如果放不进去，就找上一行同重量下最大的，如果能放进去，看看剩余的重量价值最大的加起来和上一列同重量进行比较。一直这样下去，最终，最大的就是在最后一个格子里面。

运行上面的程序，输入如下：

0([])	0([])	10(['water'])	10(['water'])	10(['water'])	10(['water'])	
3(['book'])	3(['book'])	10(['water'])	13(['water', 'book'])	13(['water', 'book'])	13(['water', 'book'])	
3(['book'])	9(['food'])	12(['book', 'food'])	13(['water', 'book'])	19(['water', 'food'])	22(['water', 'book', 'food'])	
3(['book'])	9(['food'])	12(['book', 'food'])	14(['food', 'jacket'])	19(['water', 'food'])	22(['water', 'book', 'food'])	
6(['camera'])	9(['food'])	15(['food', 'camera'])	18(['book', 'food', 'camera'])	20(['food', 'jacket', 'camera'])	25(['water', 'food', 'camera'])