0-1背包问题的python写法
时间: 2023-11-13 17:54:03 浏览: 168
使用遗传算法 在Python中解决 0-1 背包问题的简单方法_python_代码_下载
5星 · 资源好评率100%
0-1背包问题是一个经典的动态规划问题,可以使用Python进行求解。以下是一个简单的实现:
```python
def knapsack(W, wt, val, n):
K = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]
```
其中,W表示背包的容量,wt表示每个物品的重量,val表示每个物品的价值,n表示物品的数量。
阅读全文