# Backpack

## ้ข็ฎๅฐๅ

https://www.lintcode.com/problem/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.``````

## ไปฃ็ 

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

Last updated