public static int solution3(int[] w, int[] v, int capacity, int value, int index) { if (index == w.length || capacity <= 0) { return value; } if (capacity >= w[index]) { // 装 int v1 = solution3(w, v, capacity - w[index], value + v[index], index + 1); // 不装 int v2 = solution3(w, v, capacity, value, index + 1); return Math.max(v1, v2); } else { return solution3(w, v, capacity, value, index + 1); } }
时间: 2024-02-14 19:22:32 浏览: 13
这段代码是用 Java 实现的 0-1 背包问题的递归解法。其中,w 是物品的重量数组,v 是物品的价值数组,capacity 是背包的容量,value 是当前已经装进背包的物品的总价值,index 是当前考虑的物品的下标。算法的时间复杂度为 O(2^n),其中 n 是物品数量。这段代码使用了递归的方式来求解最优解,对于每一个物品,都有两种情况:装进背包或者不装进背包。如果当前物品的重量已经超过了背包的容量,则只能不装进背包。具体的算法实现可以参考这篇文章:https://www.cnblogs.com/shadowland/p/5811409.html
相关问题
public static int i;
public static final int是Java中的关键字,用于定义一个公共的静态常量。其中,public表示该常量可以被其他类访问,static表示该常量是静态的,final表示该常量是不可变的。在Java中,常量一般使用大写字母表示,例如:public static final int MAX_VALUE = 100; 表示定义了一个最大值为100的常量。
public static int gcd(int m, int n) 还可以怎么写
`public static int gcd(int m, int n)` 这个方法还可以使用递归来实现。递归方法的基本思路是:如果 m 小于 n,就交换 m 和 n 的值;然后,如果 n 等于 0,就返回 m,否则递归调用 `gcd(n, m % n)`。
下面是使用递归方式实现的代码:
```
public static int gcd(int m, int n) {
if (m < n) {
int temp = m;
m = n;
n = temp;
}
if (n == 0) {
return m;
} else {
return gcd(n, m % n);
}
}
```
递归实现的方式与循环实现的方式相比,代码看起来更加简洁,但是在计算过程中会生成多个调用栈,可能会导致栈溢出的问题。因此,在实际应用中需要注意函数的递归深度。