首页 > 代码库 > lintcode backpack
lintcode backpack
Given n items with size A[i], 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.
样例
If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 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.
解法：
背包问题。
f(j)=max(f(j=wi)+vi, f(j))
public 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 */ public int backPack(int m, int[] A) { // write your code here int[] result=new int[m+1]; for(int i=0;i<A.length;i++){ for(int j=m;j>=A[i];j--){ result[j]=Math.max(result[j-A[i]]+A[i], result[j]); } } return result[m]; }}
lintcode backpack
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。