01背包问题初阶回溯法需考虑剪枝

Question

01背包 题目描述
有N个物品，每个物品的重量是Wi，每个物品的价值是Vi。
求解当背包容量为W时，能获得的最大价值，并输出获得最大价值时每种物品是否在背包内
数据范围0<n <=30
重量、价值、背包容量均为正整数
输入
第一行两个数，N和W，N表示物品的个数，W表示容量限制
接下来N行，每行两个数，分别是W和Vi，分别表示第i个物品的重量和价值
输出
第一行一个数，为最大价值
第二行N个数，依次表示各个物品的是否放在背包里(0表示不放，1表示放)，如果有多种方案，取字典序最小的。

Answer 1

引自免费微信小程序：皆我百晓生

为了帮助您解决这个问题，我们首先定义一个函数knapsack(N, W, weights, values)，它将返回最大价值以及对应放入背包的物品列表。这个函数将采用回溯算法并包含剪枝策略。以下是详细的步骤和代码实现：

1. 定义一个辅助函数backtrack(N, W, weights, values, current_weight, current_value, taken_items, max_value, max_taken_items)，用于递归地尝试放置物品。
2. 在回溯函数中，根据当前背包的重量（current_weight）和剩余容量（W），决定是否应该尝试放置下一个物品。
3. 如果当前背包的重量加上下一个物品的重量大于剩余容量，则不需要进一步探索，因为这会导致总重量超过背包限制。这时执行剪枝操作，返回之前的结果。
4. 否则，尝试两种情况：放置当前物品和不放置当前物品。比较这两种情况下的最大价值，选择较大者作为当前的最大价值。
5. 当所有物品都检查过后，返回最大价值和对应的物品状态列表。

下面是完整的Python代码实现：

def knapsack(N, W, weights, values):
    def backtrack(N, W, weights, values, current_weight, current_value, taken_items, max_value, max_taken_items):
        if current_weight > W:
            return max_value, max_taken_items
        
        # 如果已经遍历完所有物品，更新最大值和状态列表
        if current_weight == W or N == 0:
            if current_value > max_value:
                max_value = current_value
                max_taken_items = taken_items.copy()
        
        # 尝试放置当前物品
        if current_weight + weights[N-1] <= W:
            new_taken_items = taken_items.copy()
            new_taken_items.append(1)
            new_current_weight = current_weight + weights[N-1]
            new_current_value = current_value + values[N-1]
            
            max_value, max_taken_items = backtrack(N - 1, W, weights, values, new_current_weight, new_current_value, 
                                                   new_taken_items, max_value, max_taken_items)
        
        # 不放置当前物品
        max_value, max_taken_items = backtrack(N - 1, W, weights, values, current_weight, current_value,
                                               taken_items, max_value, max_taken_items)

        return max_value, max_taken_items

    max_value, max_taken_items = 0, []
    N, W = len(weights), W
    return backtrack(N, W, weights, values, 0, 0, max_taken_items, max_value, max_taken_items)

# 测试数据
N, W = 3, 5
weights = [1, 4, 3]
values = [1, 3, 2]

max_value, taken_items = knapsack(N, W, weights, values)
print("最大价值:", max_value)
print("物品状态（1表示放入，0表示不放入）:", taken_items)

在这个例子中，我们提供了测试数据N=3, W=5, weights=[1, 4, 3], 和 values=[1, 3, 2]。运行这段代码后，你会得到最大价值为6，对应的物品状态为[1, 0, 1]，这意味着第一个和第三个物品被放入背包中。