动态规划法求解0-1背包伪代码

动态规划是解决优化问题的一种常用方法，对于0-1背包问题，它可以用来找到在给定物品价值和重量限制下，能够获得的最大总价值。下面是一个简单的动态规划算法的伪代码，假设`dp[i][w]`表示前`i`个物品中选取重量不超过`w`的物品所能获得的最大价值：

function knapsack_01(items, capacity):
    n = number_of_items(items)   # 物品数量
    dp = array(n+1, capacity+1)  # 初始化一个二维数组，行数为物品+1，列数为容量+1，初始值设为0

    for i in range(1, n+1):      # 遍历每个物品
        for w in range(capacity+1):  # 遍历所有可能的背包容量
            if items[i-1].weight <= w:  # 如果当前物品能装入背包
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i-1].weight] + items[i-1].value)  # 更新状态
            else:                   # 否则，只能不选这个物品
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]     # 返回最后的结果，即最大价值

item Struct:
    value: integer    # 物品的价值
    weight: integer   # 物品的重量

items: list of items  # 包含所有物品的列表
capacity: integer    # 背包的总重量限制