01背包问题python代码和伪代码

01背包问题是经典的动态规划问题，以下是Python代码和伪代码：

Python代码：

def knapsack(w, v, c):
    n = len(w)
    dp = [[0] * (c+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, c+1):
            if w[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
    return dp[n][c]

伪代码：

输入：物品的重量数组 w，物品的价值数组 v，背包容量 c
定义一个 n 行 c+1 列的二维数组 dp
初始化 dp[0][j] = 0，表示不选任何物品时的最大价值为 0
for i = 1 to n:
    for j = 1 to c:
        if w[i-1] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
返回 dp[n][c]，即选取物品后的最大价值

相关问题

01背包问题怎么写和伪代码怎么写

01背包问题是动态规划的经典问题之一，通常用于资源分配决策。给定一组物品，每个物品有自己的重量和价值，目标是在不超过背包容量的情况下选择最有价值的物品组合。以下是基本的伪代码描述：

// 定义函数 knapSack(W, wt[], val[], n)，
// W：背包最大容量，
// wt[]：物品重量数组，
// val[]：物品价值数组，
// n：物品数量

function knapSack(W, wt[], val[], n):
    // 初始化一个二维数组 dp[n+1][W+1]，其中 dp[i][j] 表示前i件物品在容量为j时的最大价值
    for i in range(0, n+1):
        for w in range(0, W+1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            else:
                # 如果当前物品可以放入背包且不会超过容量限制，取价值较大的选择；否则取不放物品的情况
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i]], dp[i-1][w])

    // 返回最大价值
    return dp[n][W]

在这个伪代码中，`dp[i][w]`表示在考虑了前`i`个物品且总重量不超过`w`的情况下能得到的最大价值。遍历所有可能的物品组合和背包容量，做出取与不取的选择。

回溯算法解决01背包问题的伪代码

回溯算法解决0-1背包问题的伪代码如下：

def backtrack(remaining_weights, remaining_values, capacity, current_weight, current_value):
    # 如果背包容量已满，且当前价值大于0，则找到了有效解
    if current_weight == capacity and current_value > 0:
        solutions.append((current_items, current_value))
        return
    
    # 检查剩余物品
    for i in range(len(remaining_weights)):
        # 如果还有空间，尝试加入物品i
        if current_weight + remaining_weights[i] <= capacity:
            # 更新状态
            current_weight += remaining_weights[i]
            current_value += remaining_values[i]
            
            # 继续向下探索
            backtrack(remaining_weights[:i] + remaining_weights[i+1:], 
                       remaining_values[:i] + remaining_values[i+1:], 
                       capacity, current_weight, current_value)
            
            # 回溯操作，撤消当前决策
            current_weight -= remaining_weights[i]
            current_value -= remaining_values[i]

# 初始化参数
items = ...  # 物品数量和重量列表
values = ...  # 物品的价值列表
capacity = ...  # 背包容量

# 解决问题
remaining_weights, remaining_values = zip(*sorted(zip(items, values), reverse=True))  # 排序并取余下部分
current_weight, current_value = 0, 0
solutions = []

backtrack(remaining_weights, remaining_values, capacity, current_weight, current_value)

# 返回最优解列表
for items_list, value in solutions:
    print(f"Items: {items_list}, Total Value: {value})[^1]"