0-1背包问题暴力递归
给你一系列物品的价值数组和所占背包容量的数组，给你一个有限容量的背包，求能背的背包的最大值，并返回这个最大值。 这里是不能多拿背包的，也就是这里的背包都有且只有一个。 实现如下，首先递归函数的逻辑就是:选择拿不拿当前遍历到的背包，如果拿就要选择加上当前背包的价值，并且把当前背包的所占容量也加上去，在遍历到下一个index，这里index就推动了递归的进行，并且两个终止条件分别代表的意思是如果当前情况下背包已经占有的容量大于了背包的容量，这时候返回一个不成功，此时这个背包在当前情形下是不能有的，返回一个-1，在比大小的时候就自然不会要这条分支，顺水推舟，这个已经占有的容量应该伴随递归函数。process可以理解为index及以后的所有情况的最大值。
public static void main(String[] args) {
int[] bagContain = new int[]{2, 4, 4};
int[] bagValue = new int[]{9, 1, 8};
int maxContain = 5;
int res = knapsack(bagContain, bagValue, maxContain);
System.out.println(res);
}
private static int knapsack(int[] bagContain, int[] bagValue, int maxContain) {
return process(bagContain, bagValue, 0, maxContain, 0);
}
private static int process(int[] bagContain, int[] bagValue, int index, int maxContain, int alreadyContain) {
if (alreadyContain > maxContain) {
return -1;
}
if (index == bagContain.length) {
return 0;
}
int p1 = process(bagContain, bagValue, index + 1, maxContain, alreadyContain);//不要此背包直接跳过
int p2Next = process(bagContain, bagValue, index + 1, maxContain, alreadyContain + bagContain[index]);
int p2 = -1; //要此背包的值为p2
if (p2Next != -1) {
p2 = bagValue[index] + p2Next;
}
return Math.max(p1, p2);//返回两种情况下的最大值
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-11-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读