knapsack-problems

背包问题

你是背包优化问题和资源分配方面的专家。你的目标是在容量约束下，帮助选择最优物品组合，在遵守重量、体积或其他资源限制的同时，最大化价值或利润。

初步评估

解决背包问题之前，先了解：

1. 问题类型

   • 0/1 背包？（每件物品只能取一次或不取）
   • 有界背包？（每件物品的数量有限）
   • 无界背包？（每件物品的数量不限）
   • 多重背包？（多个容器／资源）
   • 多维背包？（多个约束，例如重量和体积）

2. 物品和价值

   • 有多少种物品？（几十种、几百种、几千种）
   • 物品价值（利润、效用、优先级）是多少？
   • 物品成本（重量、体积、价格）是多少？
   • 物品之间是否存在依赖或冲突？

3. 容量约束

   • 单一约束（仅重量）还是多个约束（重量和体积）？
   • 容量限制（重量容量、体积容量、预算）是多少？
   • 是否有多个容量不同的背包？

4. 优化目标

   • 最大化总价值？
   • 在满足要求的前提下最小化总成本？
   • 多目标优化（价值与重量）？

5. 特殊要求

   • 是否有必须选入的物品？
   • 物品类别是否有配额？
   • 是否有必须整体选取或不选取的物品组？

---

背包问题框架

问题分类

1. 0/1 背包

• 每件物品最多只能选一次
• 二元决策：选入或排除
• 最常见的变体
• 应用：项目选择、有价值货物的装载

2. 有界背包

• 每件物品的可用数量有限
• 决策：每件物品取多少件（从 0 到 max_qty）
• 0/1 背包的推广
• 应用：投资组合选择、库存选择

3. 无界背包

• 每种物品的数量不限
• 可根据容量尽可能多地取用
• 应用：下料问题、硬币找零、资源采购

4. 多重背包

• 可使用多个容器／箱子
• 将物品分配到各背包，以最大化总价值
• 应用：多车辆装载、多仓库分配

5. 多维背包

• 多个容量约束（重量、体积、成本等）
• 更贴近现实，但求解难度更高
• 应用：货物装载、受多种资源约束的项目选择

6. 二次背包

• 物品价值取决于还选取了哪些其他物品
• 可体现协同效应或冲突
• 应用：产品组合、投资组合优化

---

数学建模

基本 0/1 背包

决策变量：

• 每件物品 i 对应 x_i ∈ {0, 1}
• 若选取物品 i，则 x_i = 1；否则 x_i = 0

目标函数： 最大化 Σ (v_i × x_i)

其中 v_i = 物品 i 的价值

约束条件： Σ (w_i × x_i) ≤ W

其中：

• w_i = 物品 i 的重量
• W = 背包容量

复杂度：

• NP 完全
• 存在使用动态规划的伪多项式算法

多维背包

目标函数： 最大化 Σ (v_i × x_i)

约束条件： 对于所有约束 j = 1, 2, ..., m，Σ (w_ij × x_i) ≤ W_j

其中：

• w_ij = 物品 i 消耗的第 j 种资源
• W_j = 第 j 种资源的容量
• m = 资源类型的数量

---

算法与求解方法

0/1 背包的动态规划

def knapsack_01_dynamic(values, weights, capacity):
    """
    Solve 0/1 Knapsack using Dynamic Programming

    Optimal solution with O(n*W) time complexity

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - capacity: knapsack capacity

    Returns: maximum value and selected items
    """

    n = len(values)

    # Create DP table
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    # Build DP table bottom-up
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Option 1: Don't take item i-1
            dp[i][w] = dp[i-1][w]

            # Option 2: Take item i-1 (if it fits)
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                              dp[i-1][w - weights[i-1]] + values[i-1])

    # Backtrack to find selected items
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(i-1)  # Item i-1 was selected
            w -= weights[i-1]

    selected.reverse()

    return {
        'max_value': dp[n][capacity],
        'selected_items': selected,
        'total_weight': sum(weights[i] for i in selected)
    }

# Example
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

result = knapsack_01_dynamic(values, weights, capacity)
print(f"Maximum value: {result['max_value']}")
print(f"Selected items: {result['selected_items']}")
print(f"Total weight: {result['total_weight']}")

空间优化版本

def knapsack_01_space_optimized(values, weights, capacity):
    """
    Space-optimized DP solution

    Uses O(W) space instead of O(n*W)
    """

    n = len(values)
    dp = [0] * (capacity + 1)

    for i in range(n):
        # Traverse backwards to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

0/1 背包的分支定界法

import heapq

def knapsack_branch_and_bound(values, weights, capacity):
    """
    Solve 0/1 Knapsack using Branch and Bound

    More efficient for problems where DP is too slow
    Good for large capacity values

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - capacity: knapsack capacity

    Returns: optimal solution
    """

    n = len(values)

    # Sort items by value/weight ratio (descending)
    items = [(values[i]/weights[i], values[i], weights[i], i) for i in range(n)]
    items.sort(reverse=True)

    class Node:
        def __init__(self, level, value, weight, bound, items_taken):
            self.level = level
            self.value = value
            self.weight = weight
            self.bound = bound
            self.items_taken = items_taken

        def __lt__(self, other):
            return self.bound > other.bound  # Max heap (best bound first)

    def calculate_bound(node):
        """Calculate upper bound of maximum value for this node"""
        if node.weight >= capacity:
            return 0

        bound = node.value
        j = node.level + 1
        remaining_capacity = capacity - node.weight

        # Add items greedily (fractional allowed for bound)
        while j < n and remaining_capacity >= items[j][2]:
            bound += items[j][1]
            remaining_capacity -= items[j][2]
            j += 1

        # Add fraction of next item if any capacity remains
        if j < n and remaining_capacity > 0:
            bound += (remaining_capacity / items[j][2]) * items[j][1]

        return bound

    # Initialize
    best_value = 0
    best_items = []

    # Priority queue (max heap by bound)
    root = Node(-1, 0, 0, 0, [])
    root.bound = calculate_bound(root)
    pq = []
    heapq.heappush(pq, root)

    # Branch and bound search
    while pq:
        node = heapq.heappop(pq)

        if node.bound <= best_value:
            continue  # Prune this branch

        level = node.level + 1
        if level >= n:
            continue

        # Branch 1: Include item at level
        ratio, value, weight, orig_idx = items[level]
        if node.weight + weight <= capacity:
            new_items = node.items_taken + [orig_idx]
            new_value = node.value + value
            new_weight = node.weight + weight

            if new_value > best_value:
                best_value = new_value
                best_items = new_items

            child = Node(level, new_value, new_weight, 0, new_items)
            child.bound = calculate_bound(child)

            if child.bound > best_value:
                heapq.heappush(pq, child)

        # Branch 2: Exclude item at level
        child = Node(level, node.value, node.weight, 0, node.items_taken[:])
        child.bound = calculate_bound(child)

        if child.bound > best_value:
            heapq.heappush(pq, child)

    return {
        'max_value': best_value,
        'selected_items': sorted(best_items),
        'total_weight': sum(weights[i] for i in best_items)
    }

贪心近似算法

def knapsack_greedy_approximation(values, weights, capacity):
    """
    Greedy approximation for 0/1 Knapsack

    Fast but not optimal
    Good for quick solutions or large problems

    Strategy: Sort by value/weight ratio, take best items first
    """

    n = len(values)

    # Calculate value/weight ratios
    items = [(values[i]/weights[i], values[i], weights[i], i) for i in range(n)]
    items.sort(reverse=True)

    total_value = 0
    total_weight = 0
    selected = []

    for ratio, value, weight, idx in items:
        if total_weight + weight <= capacity:
            selected.append(idx)
            total_value += value
            total_weight += weight

    return {
        'total_value': total_value,
        'selected_items': sorted(selected),
        'total_weight': total_weight
    }

有界背包

def bounded_knapsack(values, weights, quantities, capacity):
    """
    Solve Bounded Knapsack Problem

    Each item type has limited quantity available

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - quantities: list of maximum quantities for each item
    - capacity: knapsack capacity

    Returns: optimal solution with quantities
    """

    n = len(values)

    # Expand to 0/1 knapsack by duplicating items
    expanded_values = []
    expanded_weights = []
    item_map = []

    for i in range(n):
        for j in range(quantities[i]):
            expanded_values.append(values[i])
            expanded_weights.append(weights[i])
            item_map.append(i)

    # Solve as 0/1 knapsack
    result = knapsack_01_dynamic(expanded_values, expanded_weights, capacity)

    # Convert back to quantities
    item_quantities = [0] * n
    for selected_idx in result['selected_items']:
        original_item = item_map[selected_idx]
        item_quantities[original_item] += 1

    return {
        'max_value': result['max_value'],
        'item_quantities': item_quantities,
        'total_weight': result['total_weight']
    }

# Example
values = [10, 40, 30, 50]
weights = [5, 4, 6, 3]
quantities = [3, 2, 1, 4]  # Max quantity of each item
capacity = 20

result = bounded_knapsack(values, weights, quantities, capacity)
print(f"Maximum value: {result['max_value']}")
print(f"Item quantities: {result['item_quantities']}")

无界背包

def unbounded_knapsack(values, weights, capacity):
    """
    Solve Unbounded Knapsack Problem

    Unlimited quantity of each item type

    Applications: Cutting stock, coin change, resource purchasing

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - capacity: knapsack capacity

    Returns: maximum value and quantities of each item
    """

    n = len(values)

    # DP array: dp[w] = max value with capacity w
    dp = [0] * (capacity + 1)

    # For backtracking
    used_item = [-1] * (capacity + 1)

    for w in range(1, capacity + 1):
        for i in range(n):
            if weights[i] <= w:
                new_value = dp[w - weights[i]] + values[i]
                if new_value > dp[w]:
                    dp[w] = new_value
                    used_item[w] = i

    # Backtrack to find quantities
    quantities = [0] * n
    w = capacity

    while w > 0 and used_item[w] != -1:
        i = used_item[w]
        quantities[i] += 1
        w -= weights[i]

    return {
        'max_value': dp[capacity],
        'item_quantities': quantities,
        'total_weight': capacity - w
    }

# Example: Cutting steel rods
# Rod lengths and their values
values = [1, 5, 8, 9, 10, 17, 17, 20]  # Value of each length
weights = [1, 2, 3, 4, 5, 6, 7, 8]     # Length of each cut
capacity = 20  # Total rod length

result = unbounded_knapsack(values, weights, capacity)
print(f"Maximum value: {result['max_value']}")
print(f"Cuts to make: {result['item_quantities']}")

多维背包

def multidimensional_knapsack(values, constraints, capacities):
    """
    Solve Multidimensional Knapsack Problem

    Multiple resource constraints (e.g., weight AND volume)

    Parameters:
    - values: list of item values
    - constraints: 2D list where constraints[i][j] = resource j used by item i
    - capacities: list of capacity limits for each resource

    Returns: approximate solution using greedy + local search

    Note: Exact solution is NP-hard and computationally expensive
    """

    n = len(values)
    m = len(capacities)  # Number of constraints

    # Greedy initialization
    def calculate_efficiency(item_idx):
        """Calculate efficiency ratio for item"""
        # Use minimum slack across all resources
        min_slack = float('inf')
        for j in range(m):
            if constraints[item_idx][j] > 0:
                slack = capacities[j] / constraints[item_idx][j]
                min_slack = min(min_slack, slack)
        return values[item_idx] / min_slack if min_slack > 0 else 0

    # Sort by efficiency
    items = [(calculate_efficiency(i), i) for i in range(n)]
    items.sort(reverse=True)

    # Greedy selection
    selected = [False] * n
    used = [0] * m

    for efficiency, idx in items:
        # Check if item fits all constraints
        fits = True
        for j in range(m):
            if used[j] + constraints[idx][j] > capacities[j]:
                fits = False
                break

        if fits:
            selected[idx] = True
            for j in range(m):
                used[j] += constraints[idx][j]

    # Calculate solution value
    total_value = sum(values[i] for i in range(n) if selected[i])

    return {
        'total_value': total_value,
        'selected_items': [i for i in range(n) if selected[i]],
        'resource_usage': used
    }

# Example: Cargo loading with weight AND volume constraints
values = [10, 40, 30, 50, 35, 25]  # Item values
constraints = [
    # [weight, volume] for each item
    [5, 10],   # Item 0
    [4, 15],   # Item 1
    [6, 12],   # Item 2
    [3, 8],    # Item 3
    [5, 14],   # Item 4
    [4, 10]    # Item 5
]
capacities = [20, 50]  # [max weight, max volume]

result = multidimensional_knapsack(values, constraints, capacities)
print(f"Maximum value: {result['total_value']}")
print(f"Selected items: {result['selected_items']}")
print(f"Resource usage: Weight={result['resource_usage'][0]}, Volume={result['resource_usage'][1]}")

多重背包问题

def multiple_knapsack(values, weights, knapsack_capacities):
    """
    Solve Multiple Knapsack Problem

    Assign items to multiple knapsacks to maximize total value

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - knapsack_capacities: list of capacities for each knapsack

    Returns: assignment of items to knapsacks
    """

    from pulp import *

    n = len(values)
    m = len(knapsack_capacities)

    # Create problem
    prob = LpProblem("Multiple_Knapsack", LpMaximize)

    # Decision variables: x[i,j] = 1 if item i assigned to knapsack j
    x = LpVariable.dicts("assign",
                        [(i, j) for i in range(n) for j in range(m)],
                        cat='Binary')

    # Objective: maximize total value
    prob += lpSum([values[i] * x[i,j]
                   for i in range(n) for j in range(m)]), "Total_Value"

    # Constraint 1: Each item assigned to at most one knapsack
    for i in range(n):
        prob += lpSum([x[i,j] for j in range(m)]) <= 1, f"Item_{i}"

    # Constraint 2: Knapsack capacity constraints
    for j in range(m):
        prob += (lpSum([weights[i] * x[i,j] for i in range(n)]) <=
                knapsack_capacities[j]), f"Capacity_{j}"

    # Solve
    prob.solve(PULP_CBC_CMD(msg=0))

    # Extract solution
    assignments = [[] for _ in range(m)]
    total_value = 0

    for i in range(n):
        for j in range(m):
            if x[i,j].varValue and x[i,j].varValue > 0.5:
                assignments[j].append(i)
                total_value += values[i]

    return {
        'total_value': total_value,
        'assignments': assignments,
        'status': LpStatus[prob.status]
    }

# Example: Assign items to 3 trucks
values = [15, 10, 8, 20, 12, 18, 9, 14]
weights = [5, 3, 2, 6, 4, 5, 2, 4]
truck_capacities = [10, 12, 8]  # 3 trucks

result = multiple_knapsack(values, weights, truck_capacities)
print(f"Total value: {result['total_value']}")
for i, assignment in enumerate(result['assignments']):
    print(f"Truck {i+1}: Items {assignment}")

---

完整背包求解器

class KnapsackSolver:
    """
    Comprehensive Knapsack Problem Solver

    Supports multiple knapsack variants
    """

    def __init__(self):
        self.items = []
        self.capacity = None
        self.solution = None

    def add_item(self, value, weight, item_id=None, max_quantity=1, volume=None):
        """
        Add item to knapsack problem

        Parameters:
        - value: item value/profit
        - weight: item weight/cost
        - item_id: item identifier
        - max_quantity: maximum quantity (for bounded knapsack)
        - volume: item volume (for multidimensional)
        """

        if item_id is None:
            item_id = f"Item_{len(self.items)}"

        self.items.append({
            'id': item_id,
            'value': value,
            'weight': weight,
            'max_quantity': max_quantity,
            'volume': volume,
            'ratio': value / weight if weight > 0 else float('inf')
        })

    def solve_01_knapsack(self, capacity, algorithm='dp'):
        """
        Solve 0/1 Knapsack

        Parameters:
        - capacity: knapsack capacity
        - algorithm: 'dp' (dynamic programming) or 'bb' (branch-and-bound)

        Returns: optimal solution
        """

        self.capacity = capacity

        values = [item['value'] for item in self.items]
        weights = [item['weight'] for item in self.items]

        if algorithm == 'dp':
            result = knapsack_01_dynamic(values, weights, capacity)
        elif algorithm == 'bb':
            result = knapsack_branch_and_bound(values, weights, capacity)
        else:
            raise ValueError(f"Unknown algorithm: {algorithm}")

        # Enhance result with item details
        self.solution = {
            'type': '0/1 Knapsack',
            'max_value': result['max_value'],
            'total_weight': result['total_weight'],
            'capacity': capacity,
            'utilization': (result['total_weight'] / capacity * 100) if capacity > 0 else 0,
            'items': [self.items[i] for i in result['selected_items']],
            'selected_indices': result['selected_items']
        }

        return self.solution

    def solve_bounded_knapsack(self, capacity):
        """Solve Bounded Knapsack"""

        values = [item['value'] for item in self.items]
        weights = [item['weight'] for item in self.items]
        quantities = [item['max_quantity'] for item in self.items]

        result = bounded_knapsack(values, weights, quantities, capacity)

        self.solution = {
            'type': 'Bounded Knapsack',
            'max_value': result['max_value'],
            'total_weight': result['total_weight'],
            'capacity': capacity,
            'utilization': (result['total_weight'] / capacity * 100) if capacity > 0 else 0,
            'item_quantities': result['item_quantities']
        }

        return self.solution

    def solve_unbounded_knapsack(self, capacity):
        """Solve Unbounded Knapsack"""

        values = [item['value'] for item in self.items]
        weights = [item['weight'] for item in self.items]

        result = unbounded_knapsack(values, weights, capacity)

        self.solution = {
            'type': 'Unbounded Knapsack',
            'max_value': result['max_value'],
            'total_weight': result['total_weight'],
            'capacity': capacity,
            'utilization': (result['total_weight'] / capacity * 100) if capacity > 0 else 0,
            'item_quantities': result['item_quantities']
        }

        return self.solution

    def print_solution(self):
        """Print solution summary"""

        if not self.solution:
            print("No solution available")
            return

        print("=" * 70)
        print(f"KNAPSACK SOLUTION: {self.solution['type']}")
        print("=" * 70)
        print(f"Maximum Value: {self.solution['max_value']}")
        print(f"Total Weight: {self.solution['total_weight']}")
        print(f"Capacity: {self.solution['capacity']}")
        print(f"Utilization: {self.solution['utilization']:.1f}%")
        print()

        if 'items' in self.solution:
            print("Selected Items:")
            for item in self.solution['items']:
                print(f"  {item['id']}: Value={item['value']}, Weight={item['weight']}")

        elif 'item_quantities' in self.solution:
            print("Item Quantities:")
            for i, qty in enumerate(self.solution['item_quantities']):
                if qty > 0:
                    item = self.items[i]
                    print(f"  {item['id']}: Quantity={qty}, "
                          f"Total Value={item['value']*qty}, "
                          f"Total Weight={item['weight']*qty}")


# Example usage
if __name__ == "__main__":
    print("Example 1: 0/1 Knapsack")
    print("-" * 50)

    solver = KnapsackSolver()

    # Add items (value, weight)
    solver.add_item(60, 10, "Item_A")
    solver.add_item(100, 20, "Item_B")
    solver.add_item(120, 30, "Item_C")
    solver.add_item(80, 15, "Item_D")
    solver.add_item(90, 18, "Item_E")

    # Solve 0/1 knapsack
    solution = solver.solve_01_knapsack(capacity=50, algorithm='dp')
    solver.print_solution()

    print("\n" + "=" * 70 + "\n")

    print("Example 2: Bounded Knapsack")
    print("-" * 50)

    solver2 = KnapsackSolver()

    # Add items with quantities
    solver2.add_item(10, 5, "Small_Box", max_quantity=3)
    solver2.add_item(40, 4, "Medium_Box", max_quantity=2)
    solver2.add_item(30, 6, "Large_Box", max_quantity=1)
    solver2.add_item(50, 3, "Premium_Box", max_quantity=4)

    solution2 = solver2.solve_bounded_knapsack(capacity=20)
    solver2.print_solution()

---

供应链应用

项目选择

def project_portfolio_selection(projects, budget, max_projects=None):
    """
    Select optimal project portfolio given budget constraint

    Knapsack where:
    - Items = projects
    - Value = NPV or expected return
    - Weight = project cost
    """

    solver = KnapsackSolver()

    for project in projects:
        solver.add_item(
            value=project['npv'],
            weight=project['cost'],
            item_id=project['name']
        )

    solution = solver.solve_01_knapsack(capacity=budget, algorithm='dp')

    return solution

货物装载价值优化

def optimize_cargo_value(cargo_items, weight_limit, volume_limit):
    """
    Maximize cargo value given weight and volume constraints

    Multidimensional knapsack with 2 constraints
    """

    values = [item['value'] for item in cargo_items]
    constraints = [[item['weight'], item['volume']] for item in cargo_items]
    capacities = [weight_limit, volume_limit]

    solution = multidimensional_knapsack(values, constraints, capacities)

    return solution

---

常见挑战与解决方案

挑战：问题规模较大

问题：

• 数千个物品
• DP 表过大
• 计算耗时过长

解决方案：

• 使用分支定界法代替 DP
• 使用贪心近似算法快速求解
• 使用 FPTAS（全多项式时间近似方案）
• 缩减物品集并迭代求解
• 对独立子问题进行并行计算

挑战：多重约束

问题：

• 重量和体积约束
• 预算和空间限制
• 可行性检查复杂

解决方案：

• 使用多维背包问题建模
• 使用基于效率比的贪心启发式算法
• 使用整数规划求解器（Gurobi、CPLEX）
• 使用约束规划
• 使用元启发式算法（遗传算法、模拟退火）

---

输出格式

背包问题解决方案报告

问题：

• 类型：0/1 背包问题
• 物品数：20
• 容量：100 磅
• 优化目标：最大化价值

解决方案：

• 最大价值：$2,450
• 总重量：98 磅（利用率为 98%）
• 选中物品数：12

选中的物品：

物品 ID	价值	重量	价值/重量比
A001	$300	10 lbs	30.0
A005	$500	15 lbs	33.3
B003	$400	18 lbs	22.2
...	...	...	...

未选中的物品：

• 物品 C002、C005、D001（容量不足）
• 剩余机会价值：$850

---

要询问的问题

1. 背包问题的类型是什么？（0/1、有界、无界、多重）
2. 优化目标是什么？（价值、利润、效用）
3. 有哪些约束？（重量、体积、预算）
4. 有多少件物品？它们的价值和成本是多少？
5. 是否有必须包含的物品或特殊要求？
6. 这是一次性决策还是重复性问题？
7. 需要多快计算出解决方案？

---

相关技能

• optimization-modeling：用于一般优化问题
• 2d-bin-packing：用于不考虑价值优化的空间装箱
• 3d-bin-packing：用于 3D 装箱问题
• pallet-loading：用于装载优化
• multi-objective-optimization：用于多重优化准则