算法--动态规划

动态规划

• 定义
  动态规划（dynamic programming， 简称DP）： 寻找多分支下最优解

• 工作原理
  要解决一个复杂的问题，先解决其子问题（先解决子问题，再逐步解决大问题）
  这便是典型的递归思想，eg：斐波拉切数列

• 应用场景

斐波拉切数列定义如下： F(0) = 1, F(1) = 1, F(n) = F(n-1)+F(n-2) (n>=2, n属于任意正整数)

代码实现：

def fib(i: int):
    if i <= 1:
        return 1
    return fib(i-1) + fib(i-2)

【缺点】
当n取足够大的值，程序运行费时，且迭代次数太多，函数堆栈溢出。
优化方案：
用一个数字来保存曾经计算过的数据，避免重复计算动态规划

• 经典问题
  1、 背包问题
  0-1 背包
  【question】 一个容量为v的背包和一些物品。物品有两种属性，体积w和价值v，
  每种物品只有一个。要求：背包装下价值尽可能多的物品，求该最大价值，背包
  可以不被装满。
  0-1背包问题： 在最优解中，每个物品中只有两种可能，在背包中和不在背包中。
  步骤1【找子问题】：
  子问题和物品相关， 每个物品，有两种结果： 能装下和不能装下。
  > a. 报的容量比物品体积小，装不下，此时，最大价值和前 i-1 个物品的
  最大价值一样。
  > b. 容量足够装下该物品，但是装了不一定大于当前相同体积的最优值，需要
  进行比较。因此，子问题中物品数和背包容量都应该被当作变量。 子问题
  确定为背包容量时，求前i个物品所能达到的最大价值。
  步骤2【确定状态】：“状态”对应的“值” 即为背包容量时，求前i个物品所能达到的最大
  价值设为dp[i][j]。初始，dp[0]j为0， 没有物品也没有价值。
  步骤3【确定状态转移方程】：第i个物品体积为w[i]价值为v[i]， 则状态转移方程为：
  * j * j>=w, dp[i][j] = max{dp[i-1][j-w[i]]+v[i], dp[i-1][j]}

from typing import List


def dynamic_p()->List:
    items = [                               # 物品项
        {"name": "水", "weight": 3, "value": 10},
        {"name": "书", "weight": 1, "value": 3},
        {"name": "食物", "weight": 2, "value": 9},
        {"name": "小刀", "weight": 3, "value": 4},
        {"name": "衣物", "weight": 2, "value": 5},
        {"name": "手机", "weight": 1, "value": 10}
    ]
    max_capacity = 6                             # 约束条件为 背包最大承重为6
    dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]

    for row in range(1, len(items) + 1):  # row 代表行
        for col in range(1, max_capacity + 1):  # col 代表列
            weight = items[row - 1]["weight"]  # 获取当前物品重量
            value = items[row - 1]["value"]  # 获取当前物品价值
            if weight > col:  # 判断物品重量是否大于当前背包容量
                dp[row][col] = dp[row - 1][col]  # 大于直接取上一次最优结果 此时row-1代表上一行
            else:
                # 使用内置函数max()，将上一次最优结果 与 当前物品价值+剩余空间可利用价值 做对比取最大值
                dp[row][col] = max(value + dp[row - 1][col - weight], dp[row - 1][col])
    return dp

• 完全背包问题
  有N种物品和一个容量为V的背包，每种物品都有无限件可用。

第i种物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，

且价值总和最大。

from typing import List


class Thing(object):
    """
    物品类, 用于定义数据结构，
    当数据两比较大时，通常使用类，来定义数据结构
    """

    def __init__(self, weight, value):
        self.weight = weight
        self.value = value


def dynamic01(things: List[Thing], capacity: int):
    """
    01 背包问题
    :param weight:
    :param value:
    :return:
    """

    n = len(things)  # 物品个数
    v = capacity # 背包容量
    f = [0] * v # 总价值
    # 优化前 时间空间负责度为： v*n
    # for i in range(n):
    #     for j in range(v, -1, -1):
    #         f[j] = max(f[j], f[j - things[i].weight] + things[i].value)
    # 时间没有优化空间，空间优化后为n
    for i in range(n):
        for j in range(v, things[i].weight, -1):
            f[j-1] = max(f[j-1], f[j - things[i].weight - 1] + things[i].value)

    return max(f)


def dynamic02(N: int, V: int, things:List[Thing]):
    """
    完全背包问题
    :param N: 物品种类
    :param V: 背包容量
    :param things: 物品详情
    :return:
    """
    if N == 0 or V == 0:
        return 0
    dp = [0] * (V + 1)
    for i in range(N):
        for j in range(things[i].weight, V, 1):
            dp[j] = max(dp[j], dp[j-things[i].weight] + things[i].value)

    return dp[V]


def to_int(num_list: List):
    """
    将输入的字符转换成数字
    :param num_list:
    :return:
    """
    if not num_list:
        return []
    if isinstance(num_list[0], list):
        res = []
        for l in num_list:
            res.append(to_int(l))
        return res

    else:
        return [int(num) for num in num_list]

def main():
    print(f"01背包：\n")
    n = input("请输入总物品数N:")
    v = input("背包容积V:")
    n = int(n)
    v = int(v)
    array = list()
    print("请输入物品体积、价值（使用空格隔开）\n")
    while n > 0:
        arr = input()
        if arr is None:
            continue
        array.append(arr.strip().split(' '))
        n -= 1

    array = to_int(array)
    things = []
    for arr in array:
        thing = Thing(arr[0], arr[1])
        things.append(thing)

    max_value = dynamic01(things, v)

    print(max_value)