我正在學習動態規劃，并有書
當我運行下面的代碼時，它應該在 Python 中實作 0/1 背包問題，我得到以下輸出：
--- ------ ------ ------ ------
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1500 | 1500 | 1500 | 1500 |
| 0 | 1500 | 1500 | 2000 | 3500 |
| 0 | 1500 | 1500 | 2000 | 3500 |
--- ------ ------ ------ ------
3500
解決方案是正確的，但看起來這是一個巧合，因為代碼生成的表格與書中圖片中給出的表格不同。
有人可以解釋一下為什么代碼生成的表格與書中的表格不同嗎？
可能是用于生成表格的公式不同（因為效果不同 - 我可以看到它們不相同）？書里的一句話是：
# A Dynamic Programming based Python
# Program for 0-1 Knapsack problem
# Returns the maximum value that can
# be put in a knapsack of capacity W
from tabulate import tabulate
def knapSack(W, wt, val, n):
K = [[0 for x in range(W 1)] for x in range(n 1)]
# Build table K[][] in bottom up manner
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]
print(tabulate(K, tablefmt="pretty"))
return K[n][W]
# Driver code
val = [1500, 2000, 3000]
wt = [1, 3, 4]
W = 4
n = len(val)
print(knapSack(W, wt, val, n))
uj5u.com熱心網友回復：
--- ------ ------ ------ ------
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1500 | 1500 | 1500 | 1500 | guitar
| 0 | 1500 | 1500 | 2000 | 3500 | laptop
| 0 | 1500 | 1500 | 2000 | 3500 | stereo
--- ------ ------ ------ ------
3500
您的串列是[guitar, laptop, stereo]，但是在作者的解決方案中，串列是[guitar, stereo, laptop]。這就是為什么你的桌子是不同的，僅此而已。您的解決方案確實是正確的。嘗試使用作者串列運行您的解決方案：
from tabulate import tabulate
def knapSack(W, wt, val, n):
K = [[0 for x in range(W 1)] for x in range(n 1)]
# Build table K[][] in bottom up manner
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]
print(tabulate(K, tablefmt="pretty"))
return K[n][W]
# Driver code
val = [1500, 3000, 2000]
wt = [1, 4, 3]
W = 4
n = len(val)
print(knapSack(W, wt, val, n))
輸出：
--- ------ ------ ------ ------
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1500 | 1500 | 1500 | 1500 | guitar
| 0 | 1500 | 1500 | 1500 | 3000 | stereo
| 0 | 1500 | 1500 | 2000 | 3500 | laptop
--- ------ ------ ------ ------
3500
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313573.html
上一篇：反之亦然編碼值及其變數
下一篇：找到影像最佳壓縮級別的最快方法