动态规划算法解0-1背包问题代码

下面是一个基于动态规划算法的解0-1背包问题的Python代码：

def knapsack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
 
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
 
    return K[n][W]
 
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapsack(W, wt, val, n))

该算法的时间复杂度为O(nW)，其中n是物品数量，W是背包容量。

相关问题

给出动态规划算法解决0-1背包问题的代码实现，并用调试好的代码解决一个实际的0-1背包问题，背包容量及物品自拟，给出运行结果截图：包含“待装物品及其重量分别为：”，“背包容量为”，

代码实现:

def knapSack(W, wt, val, n):

    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]

    return K[n][W]

实际问题解决：

待装物品及其重量分别为：{0: 2, 1: 6, 2: 2, 3: 1}
背包容量为：10

运行结果截图：

给出完整java代码实现动态规划算法实现0-1背包问题输出选择的最大价值以及选择了哪些物品。

好的，以下是实现动态规划算法解决0-1背包问题的Java代码：

import java.util.Arrays;

public class Knapsack01 {
    public static int knapsack(int[] wt, int[] val, int W, int n) {
        int[][] dp = new int[n + 1][W + 1];
        
        // 初始化第一行和第一列为0
        for (int i = 0; i < n + 1; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j < W + 1; j++) {
            dp[0][j] = 0;
        }
        
        // 根据动态规划的思路，逐步填充dp矩阵
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < W + 1; j++) {
                if (wt[i - 1] <= j) {
                    dp[i][j] = Math.max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        // 依据dp矩阵回溯求解选中的物品集合
        int i = n, j = W;
        int totalVal = dp[n][W];
        System.out.println("选择的物品集合为：");
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i - 1][j]) {
                System.out.print(i + " ");
                j = j - wt[i - 1];
            }
            i--;
        }
        System.out.println();
        
        return totalVal;
    }

    public static void main(String[] args) {
        int[] wt = { 10, 20, 30 };
        int[] val = { 60, 100, 120 };
        int W = 50;
        int n = 3;
        int maxVal = knapsack(wt, val, W, n);
        System.out.println("选择的最大价值为：" + maxVal);
    }
}

其中，wt数组代表物品的重量，val数组代表物品的价值，W代表背包的容量，n代表物品的数量。对于这个问题，程序通过动态规划求解得到最大价值，并根据dp矩阵回溯得到选择的物品集合。如果有需要，也可以将程序调整为接收外部输入来满足更加灵活的使用场景。