Java背包问题是一种常见的动态规划问题,它涉及在有限的物品中选择最佳组合,以获得最大价值。在这种情况下,每个物品都有一个重量和一个价值,并且有一个背包,它有一个最大重量限制。问题是找到一组物品,使得它们的总重量不超过背包的最大重量,并且总价值最大。
Java背包问题是一种常见的动态规划问题,它涉及在有限的物品中选择最佳组合,以获得最大价值。在这种情况下,每个物品都有一个重量和一个价值,并且有一个背包,它有一个最大重量限制。问题是找到一组物品,使得它们的总重量不超过背包的最大重量,并且总价值最大。
是一个用于解决Java背包问题的代码:
public static int knapsack(int[] weights, int[] values, int maxWeight) {
int n = weights.length;
// matrix to store the results
int[][] dp = new int[n + 1][maxWeight + 1];
// fill the matrix
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= maxWeight; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (weights[i - 1] <= j)
dp[i][j] = Math.max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[n][maxWeight];
}
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(4条)