编写Java代码有n件物品,每件物品的重量为w[],价值为c[]。现有一个容量为V的背包,问如何选取物品放入背包,使得背包内物品的总价值最大。其中每种物品都只有一件。
时间: 2024-05-01 22:22:36 浏览: 17
这是一个典型的0/1背包问题,可以使用动态规划来解决。
定义一个二维数组dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。
则状态转移方程为:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+c[i])
其中,dp[i-1][j]表示不放第i件物品时的最大价值,dp[i-1][j-w[i]]+c[i]表示放第i件物品时的最大价值。
最终的答案为dp[n][V]。
Java代码实现如下:
```java
public int knapsack(int[] w, int[] c, int V) {
int n = w.length;
int[][] dp = new int[n+1][V+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; 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]]+c[i-1]);
}
}
}
return dp[n][V];
}
```
其中,w数组表示物品的重量,c数组表示物品的价值,V表示背包的容量。