顿搜
飞过闲红千叶，夕岸在哪
类目归类
[LintCode 92] Backpack [Java]
10/12
1. Description
Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
Notice
You can not divide any item into small pieces.
2. 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.
3. Code
public class LintCode0092 {
public int backPack(int m, int[] A) {
if (m < 0 || A == null || A.length == 0) {
return 0;
}
int[][] dp = new int[A.length + 1][m + 1];
for (int j = 0; j <= m; j++) {
dp[0][j] = 0;
}
for (int i = 0; i < A.length; i++) {
for (int j = 0; j <= m; j++) {
dp[i + 1][j] = dp[i][j];
if (j >= A[i]) {
dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - A[i]] + A[i]);
}
}
}
return dp[A.length][m];
}
public static void main(String[] args) {
LintCode0092 lintcode = new LintCode0092();
int[] A = new int[] { 3, 4, 8, 5 };
System.out.println(lintcode.backPack(10, A));
}
}
