## 92.Backpack (LintCode, 单次选择+最大体积)

### Description

Given n _items with size _Ai, an integer _m _denotes the size of a backpack. How full you can fill this backpack?

You can not divide any item into small pieces.

Have you met this question in a real interview?

Yes

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

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

Thoughts:

1. 0 - 1 backpack problem
2. Space-optimized Solution:
1. dp[j] = for size j, there is a solution for current A[0, ... i] items
2. dp = True
3. in reverse order: dp[j] |= dp[j - A[i]] # we can insert item A[i] into j
4. solution : max i such that dp[i] == 1
3. Non-optimized Solution:
1. dp[i][j]: for (i - 1) th item i, whether size j contain full bag (0th is for initial state)
2. dp[.] = True
3. in left-right order: dp[i][j] = dp[i - 1][j - A[i - 1]] for j >= A[i - 1]
4. real value Solution

Code T: 2614 ms O(m * n); S: O(m)

``````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

dp = [0 for _ in range(m + 1)]
dp = 1
for i in range( len(A) ):
for j in range(m, A[i ]-1, -1):
dp[j] |= dp[j - A[i]]

for i in range(m, -1, -1):
if dp[i]:
return i

return 0
``````

Code T: O(m * n) 6288 ms; S: O(m * n)

``````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
dp = [[0 for j in range(m + 1)] for i in range(len(A) + 1)]
for i in range(len(dp)):
dp[i] = 1
# print('m + 1: {};  n + 1: {}'.format(len(dp),len(dp)))

for i in range(1, len(A) + 1):
for j in range (m + 1):
# print('i: {}; j: {}'.format(i,j))
dp[i][j] = dp[i-1][j]
if j >= A[i-1] and dp[i - 1][j - A[i - 1]]:
dp[i][j] = 1

for j in range(m, -1 , -1):
if dp[len(A)][j]:
return j

return 0
``````

Code T: O(m * n) 2397 ms; S: O(m)

``````public class Solution {
public int backPack(int m, int[] A) {
int[] dp = new int[m+1];
for (int i = 0; i < A.length; i++) {
for (int j = m; j > 0; j--) {
if (j >= A[i]) {
dp[j] = Math.max(dp[j], dp[j-A[i]] + A[i]);
}
}
}
return dp[m];
}
}
``````