背包问题请问输出背包中装入的物品编号的代码怎么写

背包问题的输出背包中装入的物品编号的代码通常需要在动态规划算法的基础上进行实现。具体实现方式会根据不同的背包问题而有所不同。以下是一个以 01 背包问题为例的代码示例：

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]
        
    result = []
    i, w = n, W
    while i > 0 and w > 0:
        if K[i][w] != K[i-1][w]:
            result.append(i-1)
            w -= wt[i-1]
            i -= 1
        else:
            i -= 1
    result.reverse()
    return result

该算法使用一个二维数组 K 来存储计算过程中的状态，其中 K[i][w] 表示前 i 个物品放入容量为 w 的背包中所能获得的最大价值。在计算完 K 数组后，我们从数组的最后一行开始，按照逆序的方式寻找向背包内放入物品的编号。具体做法为，若 K[i][w] 跟 K[i-1][w] 相等，则代表第 i 个物品没有被选中，我们随即将 i 减1，继续向前寻找；若 K[i][w] 跟 K[i-1][w] 不相等，则代表第 i 个物品被选中，我们将其编号 i-1 添加到 result 数组中，同时将 w 减去已经放入物品的重量 wt[i-1]。

在调用该方法时，传入的参数依次代表背包的容量 W、每个物品的重量 wt、每个物品对应的价值 val，以及物品的数量 n，返回值为背包中放入物品的编号列表 result。