动态规划之背包问题--python版本

￡神魔★判官ぃ 2023-06-11 07:29 36阅读 0赞

# 动态规划之背包问题–python版本 #

## 问题 ##

> 已知一个最大量的背包，给定一组给定固定价值和固定体积的物品，求在不超过最大值的前提下，能放入背包中的最大总价值。

## 解题思路 ##

该问题是典型的动态规划问题，分为三种不同的类型（0-1背包问题、完全背包和多重背包问题）

解题关键–状态转移表达式：  
 B ( k , C ) = m a x ( B ( k − 1 , C ) , B ( k − 1 , C − c i ) + v i ) B(k,C) = max(B(k-1,C), B(k-1,C-c\_i)+v\_i) B(k,C)=max(B(k−1,C),B(k−1,C−ci)\+vi)

*  k表示总共物品为k件
 *  C表示背包总容量
 *   c i c\_i ci表示第i件物品占用容量
 *   v i v\_i vi表示第i件物品价值

# 0-1背包 #

from _ctypes import Array
    
    
    class Knapsack:
        c: Array = [0, 2, 5, 4, 3, 6]  # capacity 各个物品容量
        v: Array = [0, 3, 4, 6, 7, 6]  # value权值
        f: Array = [0 for i in range(0, 21)]  # 存放结果 需要初始化，否则数组会越界
    
        def bag_1(self, capacitySum):
            ''' 通俗算法 时间复杂度：O(capacitySum * n) 空间复杂度：O(capacitySum * n) :param capacitySum: 包的总容量 :return: 返回求解的数组的 '''
            n = len(self.c)
    
            res = [[0 for col in range(21)] for row in range(n)]
            for i in range(1, n):
                for j in range(1, capacitySum + 1):
                    if self.c[i] > j:
                        res[i][j] = res[i - 1][j]
                    else:
                        # 当前状态为 前一个状态最优解 与 选取第i件商品的价值和剩余空间最优解 的最大值
                        res[i][j] = max(res[i - 1][j], res[i - 1][j-self.c[i]] + self.v[i])
            return res
    
        def bag(self, capacitySum):
            ''' 优化空间算法 时间复杂度：O(capacitySum * n) 空间复杂度：O(capacitySum * 1) :param capacitySum: 包的总容量 :return: 返回求解的数组的 '''
            n = len(self.c)
            for i in range(1, n):
                # 此处为倒叙，正序在计算过程中不能表示上一个状态的值，被更新啦
                for j in range(capacitySum, self.c[i] - 1, -1):
                    self.f[j] = max(self.f[j], self.f[j - self.c[i]] + self.v[i])
            return self.f

## 完全背包 ##

完全背包问题是指每种物品都有无限件

## 多重背包问题 ##

多重背包问题限定了一种物品的个数，解决多重背包问题，只需要把它转化为0-1背包问题即可。比如，有2件价值为5，重量为2的同一物品，我们就可以分为物品a和物品b，a和b的价值都为5，重量都为2，但我们把它们视作不同的物品。

## 参考 ##

[背包问题：0-1背包、完全背包和多重背包][0-1]

[\[Algorithm\]\[011\] 动态规划 Dynamic Programming(DP) 背包DP 3讲 \[OTTFF\]][Algorithm_011_ _ Dynamic Programming_DP_ _DP 3_ _OTTFF]

[0-1]: https://www.cnblogs.com/fengziwei/p/7750849.html
[Algorithm_011_ _ Dynamic Programming_DP_ _DP 3_ _OTTFF]: https://www.bilibili.com/video/av70148899/?p=2