【算法-面试】动态规划专题之背包问题

# coding = "utf-8"

'''
0-1背包:https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485064&idx=1&sn=550705eb67f5e71487c8b218382919d6&chksm=9bd7f880aca071962a5a17d0f85d979d6f0c5a5ce32c84b8fee88e36d451f9ccb3bb47b88f78&scene=21#wechat_redirect
    dp[i][j]:前i个物品,背包容量为j,此时的最大价值
    状态:
        1. 装进背包(放得下)
        2. 不装进背包(放不下)
子集背包:

完全背包:物品数量是无上限的
'''


def canPartition(nums):
    '''
    给你⼀个只包含正整数的⾮空数组 nums。请你判断是否可以将这个数组分割成两个⼦集,使得两个⼦集的元素和相等。
    leetcode:416. 分割等和⼦集
    input:nums = [1,5,11,5]
    output:true
    思路:
        1. 转换问题:给一个可装载重量为sum/2的背包和N个物品,每个物品的重量为nums[i]。现在让你装物品,是否存在一种装法,能够恰好将背包装满
        2. dp[i][j] = x表示,对于前i个物品,当前背包的容量为j时,若x为true,则说明可以恰好将背包装满,若x为false,则说明不能恰好将背包装满
        3.
    '''
    n, s = len(nums), sum(nums)
    if s % 2 != 0:
        return False
    s = int(s / 2)
    dp = [[False for _ in range(s + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        # base case
        # 因为背包没有空间的时候,就相当于装满了;而当没有物品可选择的时候,肯定没办法装满背包
        dp[i][0] = True
    for i in range(1, n + 1):
        for j in range(1, s + 1):
            print(nums[i - 1], j - nums[i - 1])
            if j - nums[i - 1] < 0:
                # 装不下
                dp[i][j] = dp[i - 1][j]
            else:
                # 装得下 如果不装,则取决于上一个状态;如果装,则取决于背包剩余容量的状态
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
    print(dp[n][s])
    return dp[n][s]


def findTargetSumWays(nums, target):
    '''
    给你⼀个整数数组 nums 和⼀个整数 target,向数组中的每个整数前添加 '+' 或 '-',然后串联起所有整数,可以构造⼀个表达式。
    例如,nums = [2, 1],可以在 2 之前添加 '+',在 1 之前添加 '-',然后串联起来得到表达式 "+2-1"。
    返回可以通过上述⽅法构造的、运算结果等于 target 的不同表达式的数⽬。
    leetcode:494. ⽬标和
    input:nums = [1,1,1,1,1], target = 3
    output:5
    思路:
        1. 此题可以使用回溯法做
        2. 动态规划做法是转化问题,sum(A) = (target + sum(nums)) / 2 nums 中存在几个子集 A,使得 A 中元素的和为 (target + sum(nums)) / 2?
        3.
    '''
    n, s = len(nums), sum(nums)
    if s < target or (s + target) % 2 == 1:
        return 0
    s = int((s + target) / 2)
    dp = [[0 for _ in range(s + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        # base case 背包为0的时候,不放入也是一种选择
        dp[i][0] = 1
    for i in range(1, n + 1):
        for j in range(1, s + 1):
            if j - nums[i - 1] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]

    print(dp[n][s])
    return dp[n][s]


def change(amount, coins):
    '''
    给你⼀个整数数组 coins 表示不同⾯额的硬币(硬币个数⽆限),另给⼀个整数 amount 表示总⾦额。
    请你计算并返回可以凑成总⾦额的硬币组合数,如果任何硬币组合都⽆法凑出总⾦额,返回 0。
    leetcode: 518. 零钱兑换 II
    input: amount = 5, coins = [1, 2, 5]
    output: 4
    思路:
        1.
        2.
        3.
    '''
    n = len(coins)
    dp = [[0 for _ in range(amount + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(1, n + 1):
        for j in range(1, amount + 1):
            if j - coins[i - 1] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                # 由于硬币是无限的,所以不选择该硬币时,dp[i][j - coins[i - 1]]
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
    print(dp[n][amount])
    return dp[n][amount]


if __name__ == "__main__":
    # canPartition([1, 5, 11, 5])
    # findTargetSumWays([1, 1, 1, 1, 1], 3)
    change(5, [1, 2, 5])

上一篇:蓝桥杯python组备赛笔记(赛前必看)


下一篇:【算法-面试】动态规划专题之一维dp