> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/bei-bao-wen-ti/backpack-ke-fou-zhuang-man.md).

# Backpack(可否装满）

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

#### Example

```
Example 1:
	Input:  [3,4,8,5], backpack size=10
	Output:  9

Example 2:
	Input:  [2,3,5,7], backpack size=12
	Output:  12
	
```

#### 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.

#### Notice

You can not divide any item into small pieces.

分析

当前解是否可以从前面得到

```
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 = [False]*(m+1)
        dp[0] = True
        res = 0
        for i in range(n):
            for v in range(m,A[i]-1,-1):
                if dp[v-A[i]]:
                    dp[v] = True
                    res = max(res,v)
        return res

```