Backpack

Question

• lintcode: (92) Backpack

Problem Statement

Given n items with size $$Ai$$, an integer _m denotes the size of a backpack. How full you can fill this backpack?

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Note

You can not divide any item into small pieces.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

题解1

本题是典型的01背包问题，每种类型的物品最多只能选择一件。参考前文 Knapsack 中总结的解法，这个题中可以将背包的 size 理解为传统背包中的重量；题目问的是能达到的最大 size, 故可将每个背包的 size 类比为传统背包中的价值。

考虑到数组索引从0开始，故定义状态bp[i + 1][j]为前 i 个物品中选出重量不超过j时总价值的最大值。状态转移方程则为分A[i] > j 与否两种情况考虑。初始化均为0，相当于没有放任何物品。

题解2

接下来看看 九章算法 的题解，这种解法感觉不是很直观，推荐使用题解1的解法。

1. 状态: result[i][S] 表示前i个物品，取出一些物品能否组成体积和为S的背包
2. 状态转移方程: $$f[i][S] = f[i-1][S-A[i]] ~or~ f[i-1][S]$$ (A[i]为第i个物品的大小)
   • 欲从前i个物品中取出一些组成体积和为S的背包，可从两个状态转换得到。
     1. $$f[i-1][S-A[i]]$$: 放入第i个物品，前 $$i-1$$ 个物品能否取出一些体积和为 $$S-A[i]$$ 的背包。
     2. $$f[i-1][S]$$: 不放入第i个物品，前 $$i-1$$ 个物品能否取出一些组成体积和为S的背包。
3. 状态初始化: $$f[1 \cdots n][0]=true; ~f[0][1 \cdots m]=false$$. 前1~n个物品组成体积和为0的背包始终为真，其他情况为假。
4. 返回结果: 寻找使 $$f[n][S]$$ 值为true的最大S ($$1 \leq S \leq m$$)

• reference
• visualization

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):
        # write your code here
        n = len(A)
        dp = [0 for x in range(m+1)]
        dp[0] = 1
        ans = 0
        for item in A:
            for i in range(m,-1,-1):
                if i-item >=0 and dp[i-item] > 0:
                    ans = max(ans,i)
                    dp[i] = 1
        return ans   
sol=Solution()
A=[2, 3, 5, 7]
m=11
sol.backPack(m,A)