Lintcode 92 · 背包问题

题目描述

描述
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

你不可以将物品进行切割。

样例 1：
输入：
数组 = [3,4,8,5]
backpack size = 10
输出：
9
解释：
装4和5.

样例 2：
输入：
数组 = [2,3,5,7]
backpack size = 12
输出：
12
解释：
装5和7.

解题思路

dp[i]为当装的总重量为i的时候，是否能恰好装下某数量的物品（内容为t或者f）
因此需要做一个i从0到m的循环，判断每一个i对应的dp[i]。
dp[0] = True

解题代码

class Solution:
    """
    @param m: An integer m denotes the size of a backpack
    @param A: Given n items with size A[i]
    @return: The maximum size
    """
    def backPack(self, m, A):
        # dp[i]为当装的总重量为i的时候，是否能恰好装下某数量的物品（内容为t或者f）
        # dp[i] = if(是否在A中还有能装的下的物品)
        dp = [False] * (m + 1)
        dp[0] = True
        # 判断各个物品还能不能塞进背包
        for i in range(len(A)):
            # j为当前背包里的剩余空间，看看剩余的空间还能不能装得下A[i]
            for j in range(m, -1, -1):
                # 如果当前剩余空间还能装下A[i]，则j - A[i] >= 0
                if j - A[i] >= 0:
                    # j在比较小的时候，可能恰好就只能装得下A[i]这个物品
                    # j在比较大的时候，让dp[j]为true的方式就是dp[j - A[i]]为true，或者之前i为别的数的时候遍历到这里恰好装得下
                    dp[j] = dp[j] or dp[j - A[i]]
        # 选一个最大的dp[i]
        for i in range(m, -1, -1):
            if dp[i] is True:
                return i
        return 0

执行结果

2563 ms时间消耗
6.45 MB空间消耗
您的提交打败了88.60 %的提交