52. 攜帶研究材料（第七期模擬筆試）

題目描述

小明是一位科學家，他需要參加一場重要的國際科學大會，以展示自己的最新研究成果。他需要帶一些研究材料，但是他的行李箱空間有限。這些研究材料包括實驗設備、文獻資料和實驗樣本等等，它們各自占據不同的重量，并且具有不同的價值。

小明的行李箱所能承擔的總重量是有限的，問小明應該如何抉擇，才能攜帶最大價值的研究材料，每種研究材料可以選擇無數次，并且可以重復選擇。

輸入描述

第一行包含兩個整數，n，v，分別表示研究材料的種類和行李所能承擔的總重量?

接下來包含 n 行，每行兩個整數 wi 和 vi，代表第 i 種研究材料的重量和價值

輸出描述

輸出一個整數，表示最大價值。

輸入示例

4 5
1 2
2 4
3 4
4 5

輸出示例

10

提示信息

第一種材料選擇五次，可以達到最大值。

數據范圍：

1 <= n <= 10000;
1 <= v <= 10000;
1 <= wi, vi <= 10^9.

思路

與0-1背包的區別是，它的物品數量是無限個，因此是一個完全背包問題，對于這種問題，解決方案只是狀態轉移方程有變化，變成了dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

python題解（二維數組）

def knapsack(n, v, weight, value):dp = [[0]*(v+1) for _ in range(n)] #dp表示可以無限次使用物品0-i的前提下，裝滿容量為j的背包可以獲得的最大價值for j in range(weight[0], v+1):dp[0][j] = dp[0][j-weight[0]]+value[0]for i in range(1, n):for j in range(1, v+1):if j < weight[i]:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]]+value[i])return dp[n-1][v]n, v = map(int, input().split())
weight = []
value = []
for _ in range(n):wi, vi = map(int, input().split())weight.append(wi)value.append(vi)
max_value = knapsack(n, v, weight, value)
print(max_value)

python題解（一維數組）

注意：與0-1背包不同，要正向遍歷

def knapsack(n, v, weight, value):dp = [0]*(v+1) #dp表示目前裝滿容量為j的背包可以獲得的最大價值for i in range(0, n):for j in range(weight[i], v+1):dp[j] = max(dp[j], dp[j-weight[i]]+value[i])return dp[v]n, v = map(int, input().split())
weight = []
value = []
for _ in range(n):wi, vi = map(int, input().split())weight.append(wi)value.append(vi)
max_value = knapsack(n, v, weight, value)
print(max_value)

?