背包问题

给定一个固定容量的背包和一组物品,每个物品都有一定的重量和价值,目标是在不超过背包容量的前提下,选择物品的组合,使得背包内的总价值最大化.

0-1背包问题
- 每个物品只能选择一次
完全背包问题
- 每个物品可以选择无限次
多重背包问题
- 每个物品可以选择有限次

解法:动态规划(Dynamic Programming,DP)

0-1背包问题

设定一个二维数组 dp[i][w],表示前 i 个物品在总重量不超过 w 的情况下可以获得的最大价值
状态转移方程为:dp[i][w]=max(dp[i−1][w],dp[i−1][w−weight[i]]+value[i])
边界条件dp[0][w]=0 for any w

对于第 i 个物品,有两种选择:

不选择该物品,价值等于上一个状态的最大价值 dp[i-1][w]
选择该物品,价值等于上一个状态中减去该物品重量后所能获得的最大价值,加上该物品的价值 dp[i-1][w - weight[i]] + value[i]

from itertools import combinations

ARRAY = [129, 146, 40, 139, 227, 38, 139, 2, 100, 200, 55]
TARGET = 1000


def closest_sum_greater_than_target(arr):
    closest_sum = float('inf')
    best_combination = []

    for r in range(1, len(arr) + 1):
        for combination in combinations(arr, r):
            current_sum = sum(combination)
            if TARGET <= current_sum < closest_sum:
                closest_sum = current_sum
                best_combination = combination
    print(closest_sum, best_combination)


if __name__ == '__main__':
    closest_sum_greater_than_target(ARRAY)

完全背包问题

数组 dp,其中 dp[j] 表示当背包容量为 j 时,所能获得的最大价值
不选择第 i 个物品:dp[j] = dp[j]
选择第 i 个物品:dp[j] = dp[j - weight[i]] + value[i]
状态转移方程为:dp[j]=max(dp[j],dp[j−weight[i]]+value[i])

def complete_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        for j in range(weights[i], capacity + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[capacity]

# 例子
weights = [1, 3, 4]
values = [15, 20, 30]
capacity = 4
print(complete_knapsack(weights, values, capacity))  # 输出：60

多重背包问题

将多重背包问题转化为0-1背包问题的多个子问题.如:某个物品可以选择3次,我们可以将它“展开”成3个相同但独立的物品
状态转移方程与0-1背包问题类似,但需要考虑每个物品的可用数量

def multiple_knapsack(weights, values, quantities, capacity):
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        for k in range(quantities[i]):
            for j in range(capacity, weights[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[capacity]

# 例子
weights = [1, 3, 4]
values = [15, 20, 30]
quantities = [2, 3, 1]  # 每个物品的最大选择次数
capacity = 7
print(multiple_knapsack(weights, values, quantities, capacity))  # 输出：95

给定一个固定容量的背包和一组物品,每个物品都有一定的重量和价值,目标是在不超过背包容量的前提下,选择物品的组合,使得背包内的总价值最大化.

解法:动态规划(Dynamic Programming,DP)

最新文章

分类