背包问题非递归算法程序

背包问题是一个经典的动态规划问题，可以使用非递归算法来解决。以下是一个使用动态规划的非递归算法程序：

def knapsack(W, wt, val, n):
    # 创建一个二维数组来存储子问题的最优解
    dp = [[0 for x in range(W+1)] for x in range(n+1)]
 
    # 填充dp数组
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                dp[i][w] = 0
            elif 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]

其中，W是背包的容量，wt是每个物品的重量数组，val是每个物品的价值数组，n是物品数量。程序首先创建一个二维数组dp，用于存储最优解。接着，程序使用两个for循环来填充dp数组。在填充过程中，程序检查当前物品是否可以放入背包中。如果可以放入，则程序选择放入或不放入当前物品，以获得最大的价值。最后，程序返回dp数组的最后一个元素，即为问题的最优解。