一站式解决背包问题

September 24, 2020

概述

背包问题是动态规划算法的一个很形象的例子，由于简单直接的特质，便于入门的同学理解动态规划算法的本质。

本文中主要实现了0-1背包、完全背包、多重背包 的基础解法，以及优化空间复杂度之后的解法。想要详细了解更多背包问题的同学，可以参考巨佬的《背包九讲》。仅供参考。

代码实现

# @Author: feiyun
# @Date: 2020-09-24
# 0-1背包
def zero_pack_2(limit, mat):
    """
    二维数组的方式
    """
    n = len(mat)
    # 对齐i
    mat = [[0, 0]] + mat
    dp = [[0 for i in range(limit + 1)] for j in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(mat[i][0], limit + 1):
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - mat[i][0]] + mat[i][1])
    return dp[n][limit]


def zero_pack_1(limit, mat):
    """
    一维数组实现
    """
    n = len(mat)
    mat = [[0, 0]] + mat
    dp = [0 for _ in range(limit + 1)]
    for i in range(1, n + 1):
        # 倒序填表，保证引用值在引用之前未被刷新
        for j in range(limit, mat[i][0] - 1, -1):
            dp[j] = max(dp[j], dp[j - mat[i][0]] + mat[i][1])
    return dp[limit]


# 完全背包
def complete_pack_2(limit, mat):
    """
    完全背包问题-二维数组基础解法
    """
    n = len(mat)
    mat = [[0, 0]] + mat
    dp = [[0 for _ in range(limit + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(limit + 1):
            dp[i][j] = dp[i - 1][j]
            for k in range(1, (j // mat[i][0]) + 1):
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * mat[i][0]] + k * mat[i][1])
    return dp[n][limit]


def complete_pack_1_(limit, mat):
    """
    完全背包--一维数组--包含k
    """
    n = len(mat)
    mat = [[0, 0]] + mat
    dp = [0 for i in range(limit + 1)]
    for i in range(1, n + 1):
        for j in range(limit, mat[i][0] - 1, -1):
            for k in range(0, j // mat[i][0] + 1):
                dp[j] = max(dp[j], dp[j - k * mat[i][0]] + k * mat[i][1])
    return dp[limit]


def complete_pack_1(limit, mat):
    """
    完全背包问题-一维数组空间优化
    """
    n = len(mat)
    mat = [[0, 0]] + mat
    dp = [0 for i in range(limit + 1)]
    for i in range(1, n + 1):
        for j in range(mat[i][0], limit + 1):
            dp[j] = max(dp[j], dp[j - mat[i][0]] + mat[i][1])
    return dp[limit]


# 多重背包问题
def multi_pack_2(limit, mat):
    """
    多重背包问题基础解法
    """
    n = len(mat)
    mat = [[0, 0, 0]] + mat
    dp = [[0 for _ in range(limit + 1)] for j in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(limit + 1):
            dp[i][j] = dp[i - 1][j]
            for k in range(min(mat[i][0], j // mat[i][1]) + 1):
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * mat[i][1]] + k * mat[i][2])
                # if j >= k * mat[i][1]:
                #     dp[i][j] = max(dp[i][j], dp[i - 1][j - (k * mat[i][1])] + (k * mat[i][2]))
                # else:
                #     dp[i][j] = max(dp[i][j], dp[i - 1][j])
                #     break
    return dp[n][limit]


def multi_pack_1(limit, mat):
    """
    多重背包空间优化
    """
    n = len(mat)
    mat = [[0, 0, 0]] + mat
    dp = [0 for _ in range(limit+1)]
    for i in range(1, n + 1):
        for j in range(limit, -1, -1):
            for k in range(1, min(mat[i][0], j // mat[i][1]) + 1):
                dp[j] = max(dp[j], dp[j - k * mat[i][1]] + k * mat[i][2])
    return dp[limit]

if __name__ == "__main__":
    # limit = 8
    # mat = [[3, 4], [5, 5], [1, 2], [2, 1], [2, 3]]
    # print("zero_pack_2:{}".format(zero_pack_2(limit, mat)))
    # print("zero_pack_1:{}".format(zero_pack_1(limit, mat)))
    # ==================================================
    # limit = 5
    # mat = [[1, 2], [2, 4], [3, 4], [4, 5]]
    # print("complete_pack_2:{}".format(complete_pack_2(limit, mat)))
    # print("complete_pack_1:{}".format(complete_pack_1(limit, mat)))
    # print("complete_pack_1_:{}".format(complete_pack_1_(limit, mat)))
    # ==================================================
    limit = 10
    mat = [[2, 2, 3], [1, 5, 10], [2, 4, 12]]
    print(multi_pack_2(limit, mat))
    print(multi_pack_1(limit, mat))

一站式解决背包问题

概述

目录

代码实现