小数背包问题的复杂度分析

# 1. 引言

- 1.1 问题背景
- 1.2 小数背包问题概述
- 1.3 目的与意义

# 2. 动态规划解法

### 2.1 动态规划基础概念回顾

动态规划（Dynamic Programming）是一种在计算机科学中使用的一种解决问题的方法。它通常用于优化问题，通过将问题分解为子问题来简化复杂问题，从而实现更高效的求解过程。

动态规划的核心思想是记忆化搜索，即将子问题的解存储起来，避免重复计算，从而提高算法效率。它常常用于解决具有重复子问题和最优子结构性质的问题。

### 2.2 小数背包问题的动态规划算法实现

下面是小数背包问题的动态规划算法实现（Python版本）：

def fractional_knapsack_dp(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for w in range(1, capacity+1):
        max_val = 0
        for i in range(n):
            if weights[i] <= w:
                max_val = max(max_val, dp[w - weights[i]] + values[i])
        dp[w] = max_val

    return dp[capacity]

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

max_value = fractional_knapsack_dp(weights, values, capacity)
print("The maximum value that can be obtained is:", max_value)

### 2.3 复杂度分析

在动态规划解法中，时间复杂度为O(n*W)，其中n为物品数量，W为背包容量。空间复杂度为O(W)。动态规划算法通过填表的方式，自底向上地计算子问题的最优解，在避免重复计算的前提下，高效地求解了小数背包问题。

# 3. 贪心算法解法

在小数背包问题中，贪心算法是一种常用的解法。本章将介绍贪心算法的基础概念，以及如何应用贪心算法来解决小数背包问题。

#### 3.1 贪心算法基础概念回顾

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。贪心算法不像动态规划算法那样需要考虑子问题的结果，它通常对问题进行一次遍历，做出即时的局部最优选择。

#### 3.2 小数背包问题的贪心算法实现

对于小数背包问题，贪心算法的实现思路通常是按照单位价值（即物品的价值与重量的比值）从大到小进行排序，然后依次选择单位价值最高的物品放入背包，直至背包装满或物品耗尽。如果物品可以分割，则可以部分放入背包。

def fractional_knapsack(values, weights, capacity):
    n = len(values)
    index = list(range(n))
    ratio = [v/w for v, w in zip(values, weights)]