問題介紹：
你得到一套金條，你的目標是盡可能多地把金條裝進你的包里。每個條形圖只有一個副本，對于每個條形圖，您可以選擇或不接受（因此您不能選擇一個條形圖的一小部分）。
問題描述：
任務。給定 ?? 金條，找出裝進一袋容量 ?? 的黃金的最大重量。
輸入格式。輸入的第一行包含一個背包的容量 ?? 和金條的數量 ??。下一行包含 ?? 整數 ??0, ??1, 。. . , ?????1 定義金條的重量。
約束。1 ≤ ?? ≤ 10? ; 1≤??≤300；0 ≤ ??0, . . . , ?????1 ≤ 10?。
輸出格式。輸出可裝入容量為 ?? 的背包的最大黃金重量。
我的代碼如下：
# Uses python3
import sys
def optimal_weight(W, w):
# write your code here
n = len(w)
value = [[0] * (W 1) for i in range(n 1)]
for i in range(1, n 1):
for j in range(1, W 1):
value[i][j] = value[i-1][j]
# does not check every single possible weight
# must loop through all diagonally top left cells
v = w[i-1] value[i-1][j-w[i-1]]
if v <= j:
value[i][j] = max(v, value[i][j])
return value[n][W]
if __name__ == '__main__':
input = sys.stdin.read()
W, n, *w = list(map(int, input.split()))
print(optimal_weight(W, w))
我的解決方案適用于給定的示例測驗用例，但被其中一個測驗用例拒絕：
失敗案例 #7/14：錯誤答案
錯誤輸出格式：串列索引超出范圍
?（使用時間：0.01/10.00，使用記憶體：11313152/2147483648。）
我可以知道可能導致錯誤的原因，或者是否有更好的方法來實施針對此問題的 DP 解決方案？
uj5u.com熱心網友回復：
我認為唯一可能的原因是以下宣告：
v = w[i-1] value[i-1][j-w[i-1]]
沒有任何約束決定這j-w[i-1]將是一個有效的索引。只需將其替換為
if j-w[i-1] >= 0:
v = w[i-1] value[i-1][j-w[i-1]]
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/472649.html
上一篇：長度為5的回文子序列數
下一篇：洗掉注釋之間的部分字串以及注釋