(weight, value, totalWeight)
| 27 | |
| 28 | # 解决0-1背包问题 |
| 29 | def maxBag(weight, value, totalWeight): |
| 30 | if len(weight) <= 0 or len(value) <= 0 or totalWeight <= 0 or len(weight) != len(value): |
| 31 | return |
| 32 | num = len(weight) |
| 33 | tempMat = [] |
| 34 | for i in range(num+1): |
| 35 | tempMat.append([0]*(totalWeight+1)) |
| 36 | for i in range(1, num+1): |
| 37 | for j in range(1, totalWeight+1): |
| 38 | if j - weight[i-1] >= 0: |
| 39 | tempMat[i][j] = max(tempMat[i-1][j], value[i-1] + tempMat[i-1][j-weight[i-1]]) |
| 40 | else: |
| 41 | tempMat[i][j] = tempMat[i-1][j] |
| 42 | return tempMat[-1][-1] |
| 43 | |
| 44 | weight, value, totalWeight = [2,1,3,2], [12,10,20,15], 5 |
| 45 | print(maxBag(weight, value, totalWeight)) |
no outgoing calls
no test coverage detected