背包问题非递归算法伪代码

以下是背包问题的非递归算法伪代码：

knapsack(W, wt, val, n):
    // W: 背包容量，wt: 物品重量数组，val: 物品价值数组，n: 物品数量
    dp = 二维数组，大小为 (n+1) x (W+1)
    
    // 初始化 dp 数组
    for i = 0 to n:
        for w = 0 to W:
            if i == 0 or w == 0:
                dp[i][w] = 0
            else if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][W]

其中，`dp[i][w]` 表示在前 `i` 个物品中，背包容量为 `w` 的情况下所能获得的最大价值。`wt[i-1]` 和 `val[i-1]` 分别表示第 `i` 个物品的重量和价值，因为数组下标是从 0 开始的，所以需要减去 1。最终返回 `dp[n][W]`，表示在前 `n` 个物品中，背包容量为 `W` 的情况下所能获得的最大价值。