给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的含量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?返回法java代码
时间: 2023-10-03 19:04:55 浏览: 33
以下是动态规划的Java代码实现:
```
public class Knapsack {
public static int knapsack(int[] w, int[] v, int C) {
int n = w.length;
int[][] dp = new int[n + 1][C + 1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= C; j++) {
if (j < w[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
}
return dp[n][C];
}
public static void main(String[] args) {
int[] w = {2, 3, 4, 5};
int[] v = {3, 4, 5, 6};
int C = 8;
System.out.println(knapsack(w, v, C));
}
}
```
其中,`w` 数组表示物品的重量,`v` 数组表示物品的价值,`C` 表示背包的容量。函数返回最大的总价值。