部分背包问题 ## 题目描述 阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N <= 100) 堆金币，第 i 堆金币的总重量和总价值分别是 m_i,v_i(1<= m_i,v_i <= 100)。阿里巴巴有一个承重量为 T(T <= 1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

这是一个经典的背包问题，可以使用动态规划来解决。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 堆金币中，背包容量为 j 时的最大总价值。

根据题目要求，我们可以得到以下状态转移方程：
- 当 i=0 或 j=0 时，dp[i][j] = 0，表示没有金币或背包容量为0时的最大总价值为0；
- 当 m_i > j 时，表示第 i 堆金币的重量大于背包容量，无法装入背包，所以 dp[i][j] = dp[i-1][j]，即不选择第 i 堆金币；
- 当 m_i <= j 时，表示第 i 堆金币的重量小于等于背包容量，可以选择装入或不装入背包。如果选择装入，则 dp[i][j] = max(dp[i-1][j], dp[i-1][j-m_i] + v_i)，即选择第 i 堆金币和不选择第 i 堆金币中的最大值；如果不选择装入，则 dp[i][j] = dp[i-1][j]；
最终，dp[N][T] 即为所求的最大总价值。

以下是一个动态规划的实现示例（使用Python语言）：

def max_value(N, T, m, v):
    dp = [[0] * (T+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, T+1):
            if m[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-m[i-1]] + v[i-1])
    return dp[N][T]
    
# 示例输入
N = 3
T = 5
m = [2, 3, 4]
v = [3, 4, 5]

# 输出最大总价值
print(max_value(N, T, m, v))  # 输出：9

在示例输入中，有3堆金币，背包容量为5。第一堆金币重量为2，价值为3；第二堆金币重量为3，价值为4；第三堆金币重量为4，价值为5。通过动态规划计算，阿里巴巴最多可以拿走的价值为9。