领扣LintCode算法问题答案-92. 背包问题
目录
92. 背包问题描述样例 1：样例 2：
题解鸣谢
92. 背包问题
描述
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
你不可以将物品进行切割。
样例 1：
输入: [3,4,8,5], backpack size=10
输出: 9
样例 2：
输入: [2,3,5,7], backpack size=12
输出: 12
题解
public class Solution {
public int backPack(int m
, int[] A
) {
int n
= A
.length
;
if (n
== 0
|| m
== 0) {
return 0;
}
int[] dp
= new int[m
+ 1];
for (int i
= 0; i
< n
; i
++) {
for (int j
= m
; j
>= A
[i
]; j
--) {
dp
[j
] = Integer
.max(dp
[j
], dp
[j
- A
[i
]] + A
[i
]);
}
}
return dp
[m
];
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
