侧边栏壁纸
  • 累计撰写 106 篇文章
  • 累计创建 3 个标签
  • 累计收到 19 条评论
标签搜索

目 录CONTENT

文章目录

动态规划解决背包问题

卑微幻想家
2022-05-31 / 0 评论 / 0 点赞 / 95 阅读 / 2,993 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

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

问题描述

假设你要去野营。你有一个容量为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'])	
0

评论区