实现一个动态规划算法，解决背包问题

本文主要是介绍实现一个动态规划算法，解决背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

public class Test_31 {// 动态规划解决0-1背包问题public int knapsack(int capacity, int[] weights, int[] values, int n) {// 创建一个二维数组dp，用于记录状态转移过程int[][] dp = new int[n + 1][capacity + 1];// 遍历物品for (int i = 1; i <= n; i++) {// 遍历背包容量for (int w = 1; w <= capacity; w++) {if (weights[i - 1] > w) {// 当前物品重量大于背包容量，无法放入，取上一个状态的值dp[i][w] = dp[i - 1][w];} else {// 否则比较放入当前物品和不放入当前物品两种情况的最大价值dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);}}}// 返回背包问题的最优解return dp[n][capacity];}public static void main(String[] args) {Test_31 knapsackProblem = new Test_31();int capacity = 15;int[] weights = {2, 3, 4, 5};int[] values = {3, 4, 5, 6};int n = weights.length;// 计算获得的最大价值int maxValue = knapsackProblem.knapsack(capacity, weights, values, n);System.out.println("The maximum value that can be obtained is: " + maxValue);}
}

这篇关于实现一个动态规划算法，解决背包问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---