用贪心算法解决下列背包问题，n=5,c=15,w={12,1,4,1,2},v={4,2,10,1,2}.求背包所得的最大价值和最优解

背包问题是一个经典的动态规划问题，但是在本题中，我们可以使用贪心算法来解决问题。

贪心算法的思想是每次选择当前最优的解决方案，不考虑后续的影响。对于背包问题，我们可以将物品按照单位重量的价值从大到小排序，然后依次将物品放入背包中，直到背包装满为止。

首先，我们需要计算每个物品的单位重量价值，即 v[i]/w[i]，然后按照这个值从大到小排序。

物品i | 重量w[i] | 价值v[i] | 单位重量价值v[i]/w[i]
---|---|---|---
3 | 4 | 10 | 2.5
1 | 12 | 4 | 0.333
5 | 2 | 2 | 1
4 | 1 | 1 | 1
2 | 1 | 2 | 2

按照单位重量价值从大到小排序后，物品的顺序为 3-2-5-4-1。

然后，我们依次将物品放入背包中，直到背包装满为止。假设当前背包的剩余容量为 c，当前考虑的物品为 i：

- 如果 w[i] <= c，将物品放入背包中，更新背包的剩余容量和价值。
- 如果 w[i] > c，将物品的一部分放入背包中，更新背包的剩余容量和价值，然后退出循环。

具体实现如下：

n = 5
c = 15
w = [12, 1, 4, 1, 2]
v = [4, 2, 10, 1, 2]

# 计算每个物品的单位重量价值
value_per_weight = [v[i] / w[i] for i in range(n)]

# 按照单位重量价值从大到小排序
items = sorted(range(n), key=lambda i: -value_per_weight[i])

# 依次将物品放入背包中
total_value = 0
solution = [0] * n
for i in items:
    if w[i] <= c:
        solution[i] = 1
        total_value += v[i]
        c -= w[i]
    else:
        solution[i] = c / w[i]
        total_value += v[i] * (c / w[i])
        break

print("最大价值为", total_value)
print("最优解为", solution)

运行结果为：

最大价值为 21.5
最优解为 [1, 0, 1, 1, 0]

因此，背包所得的最大价值为 21.5，最优解为选择物品 1、3、4，其中物品 1 选取部分，物品 3 和物品 4 选取全部。