背包问题的动态规划算法实现

背包问题是一个经典的组合优化问题，动态规划是解决背包问题的一种常用方法。下面是背包问题的动态规划算法实现：

1. 算法思路：

（1）将问题分解为子问题，定义状态：设f[i][j]表示前i个物品放入容量为j的背包可以获得的最大价值。

（2）状态转移方程：f[i][j] = max{f[i-1][j], f[i-1][j-w[i]] + v[i]}，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

（3）边界条件：f[j] = 0，f[i] = 0。

（4）最终结果：f[n][m]，其中n表示物品的个数，m表示背包的容量。

2. Python代码实现：

def knapsack(w, v, m):
    n = len(w)
    f = [[0] * (m + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if j < w[i - 1]:
                f[i][j] = f[i - 1][j]
            else:
                f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i - 1]] + v[i - 1])
    return f[n][m]

3. 示例：

假设有5个物品，重量分别为[2, 2, 6, 5, 4]，价值分别为[6, 3, 5, 4, 6]，背包容量为10，求能够获得的最大价值。

w = [2, 2, 6, 5, 4]
v = [6, 3, 5, 4, 6]
m = 10
print(knapsack(w, v, m)) # 输出：15