完全背包问题 java实现
时间: 2023-12-10 11:04:24 浏览: 23
public class KnapsackProblem {
public static void main(String[] args) {
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
int result = knapsack(weights, values, capacity);
System.out.println("Maximum value: " + result);
}
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (weights[i - 1] <= j) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][capacity];
}
}