ratio = [(values[i] / weights[i], i) for i in range(n)]复杂化
时间: 2023-07-09 14:18:42 浏览: 42
如果要复杂化这个比例列表的生成,可以引入一个参数 `power`,用来控制对价值和重量的影响程度。将每个物品的比例计算公式修改为:`(values[i] ** power / weights[i], i)`,即将价值的指数设为 `power`,这样可以调整价值和重量在计算比例时的影响程度,进而影响排序结果。当 `power=1` 时,即为正常的性价比计算。
以下是代码实现:
```python
def knapsack(capacity, weights, values, power=1):
n = len(weights)
ratio = [(values[i] ** power / weights[i], i) for i in range(n)]
ratio.sort(reverse=True)
max_value = 0
for r, i in ratio:
if capacity >= weights[i]:
max_value += values[i]
capacity -= weights[i]
else:
max_value += r * capacity
break
return max_value
# 测试
capacity = 50
weights = [10, 20, 30]
values = [60, 100, 120]
print(knapsack(capacity, weights, values, power=1.2)) # 输出245
```
在这个例子中,我们将 `power` 设为 `1.2`,表示将价值的指数设为 `1.2`。这样修改后,比例列表的生成方式会受到影响,从而影响排序结果。在计算最大价值时,我们会发现装入背包的物品发生了变化,导致最大价值也发生了变化,从220变为了245。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)