给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100),价值为vi(vi<=100),背包的容量为C(C<=1000)。 应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品i只有两个选择:装入或不装入。不能将物品i装入多次,也不能只装入部分物品i,用java代码解决
时间: 2023-03-14 09:59:57 浏览: 106
给定n种物品和一个背包
5星 · 资源好评率100%
这是一个典型的01背包问题。
解决这个问题的常用方法是使用动态规划。
我们可以使用一个二维数组 $dp[i][j]$ 来表示,在前 $i$ 种物品中选择若干个物品,使得它们的总重量不超过 $j$ 时,所能达到的最大价值。
状态转移方程如下:
$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)$
代码如下:
```java
int n = 100; // 物品的数量
int C = 1000; // 背包的容量
int[] w = new int[n+1]; // 物品的重量
int[] v = new int[n+1]; // 物品的价值
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]) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
}
}
}
// 输出最大价值
System.out.println(dp[n][C]);
```
注意:在实际实现中,可以使用一维数组滚动更新,从而将空间复杂度降低至 $O(C)$。
阅读全文