b030: 隨選視訊
小綠購買了某線上影視公司提供的隨選視訊方案，只要付一筆費用，就可以觀看總長度 M 分鐘的影片，小綠從該公司提供的影片中挑選了 N 部有興趣的電影，每部電影都有不同的長度以及滿足感，請問你小綠該如何選擇，才能得到最大的滿足感。挑選影片的限制如下：
小綠購買了某線上影視公司提供的隨選視訊方案，只要付一筆費用，就可以觀看總長度 M 分鐘的影片，小綠從該公司提供的影片中挑選了 N 部有興趣的電影，每部電影都有不同的長度以及滿足感，請問你小綠該如何選擇，才能得到最大的滿足感。挑選影片的限制如下：
- 影片一定要從頭看到尾，只看一半得不到任何的滿足感。
- 同一部影片只需要看一次，看兩次以上滿足感並不會增加。
- 影片的觀賞順序並不會影響它們的滿足感。
輸入說明：
第一行有兩個正整數 N、M (1<=N<=100、1<=M<=1000)，N 為小綠感興趣的影片數，M 為小綠可以觀賞的影片總長度。接下來有 N 行影片的資料，每行有兩個正整數 L、S (1<=L<=100、1<=S<=500)，L 為該影片的長度，S 為該影片的滿足感。
輸出說明：
請輸出以 M 為最大總長度時，小綠可以得到的最大滿足感是多少。
範例輸入：
4 9 2 3 3 4 4 5 5 6
範例輸出 ：
12
背包問題（Knapsack Problem）
說明
假設有一個背包的負重最多可達8公斤，而希望在背包中裝入負重範圍內可得之總價物品，假設是水果好了，水果的編號、單價與重量如下所示：| 0 | 李子 | 4KG | NT$4500 |
| 1 | 蘋果 | 5KG | NT$5700 |
| 2 | 橘子 | 2KG | NT$2250 |
| 3 | 草莓 | 1KG | NT$1100 |
| 4 | 甜瓜 | 6KG | NT$6700 |
解法
背包問題是關於最佳化的問題，要解最佳化問題可以使用「動態規劃」（Dynamic programming），從空集合開始，每增加一個元素就先求出該階段的最佳解，直到所有的元素加入至集合中，最後得到的就是最佳解。以背包問題為例，我們使用兩個陣列value與item，value表示目前的最佳解所得之總價，item表示最後一個放至背包的水果，假設有負重量 1～8的背包8個，並對每個背包求其最佳解。
逐步將水果放入背包中，並求該階段的最佳解：
- 放入李子
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | ０ | ０ | ０ | 4500 | 4500 | 4500 | 4500 | 9000 |
| item | － | － | － | ０ | ０ | ０ | ０ | ０ |
- 放入蘋果
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | ０ | ０ | ０ | 4500 | 5700 | 5700 | 5700 | 9000 |
| item | － | － | － | ０ | 1 | 1 | 1 | ０ |
- 放入橘子
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | ０ | 2250 | 2250 | 4500 | 5700 | 6750 | 7950 | 9000 |
| item | － | 2 | 2 | ０ | 1 | 2 | 2 | ０ |
- 放入草莓
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 1100 | 2250 | 3350 | 4500 | 5700 | 6800 | 7950 | 9050 |
| item | 3 | 2 | 3 | ０ | 1 | 3 | 2 | 3 |
- 放入甜瓜
| 背包負重 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 1100 | 2250 | 3350 | 4500 | 5700 | 6800 | 7950 | 9050 |
| item | 3 | 2 | 3 | ０ | 1 | 3 | 2 | 3 |
由最後一個表格，可以得知在背包負重8公斤時，最多可以裝入9050元的水果，而最後一個裝入的 水果是3號，也就是草莓，裝入了草莓，背包只能再放入7公斤（8-1）的水果，所以必須看背包負重7公斤時的最佳解，最後一個放入的是2號，也就 是橘子，現在背包剩下負重量5公斤（7-2），所以看負重5公斤的最佳解，最後放入的是1號，也就是蘋果，此時背包負重量剩下0公斤（5-5），無法 再放入水果，所以求出最佳解為放入草莓、橘子與蘋果，而總價為9050元。
#A naive recursive implementation of 0-1 Knapsack Problem
# Returns the maximum value that can be put in a knapsack of
# capacity W
def knapSack(W , wt , val , n):
# Base Case
if n == 0 or W == 0 :
return 0
# If weight of the nth item is more than Knapsack of capacity
# W, then this item cannot be included in the optimal solution
if ((wt[n-1]) > W):
return knapSack(W , wt , val , n-1)
# return the maximum of two cases:
# (1) nth item included
# (2) not included
else:
return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1),
knapSack(W , wt , val , n-1))
# end of function knapSack
# To test above function
#val = [3,4,5,6]
#wt = [2,3,4,5]
#W = 9
# 輸入多行資料
# get multiline input from user [duplicate]
print("正整數 M 1<=M<=1000) ,M 為小綠可以觀賞的影片總長度")
W=int(input("--> "))
wt = []
print("請輸入數字 代表L為該影片的長度 或按enter結束")
while True:
line_in = input()
if line_in:
wt.append(line_in)
else:
break
print(wt)
wt = list(map(int, wt)) #Convert all strings in a list to int
val = []
print("請輸入數字 S 為該影片的滿足感 或按enter結束")
while True:
line_in = input()
if line_in:
val.append(line_in)
else:
break
print(val)
val = list(map(int, val)) #Convert strings in a list to int
n = len(val)
print(W,"為最大總長度時，小綠可以得到的最大滿足感是",end='')
print (knapSack(W , wt , val , n))
# This code is contributed by Nikhil Kumar Singh
=== ===== RESTART: F:/Python_APSC/b030.py ======================
正整數 M 1<=M<=1000) ,M 為小綠可以觀賞的影片總長度
--> 9
請輸入數字 代表L為該影片的長度 或按enter結束
2
3
4
5
['2', '3', '4', '5']
請輸入數字 S 為該影片的滿足感 或按enter結束
3
4
5
6
['3', '4', '5', '6']
9 為最大總長度時，小綠可以得到的最大滿足感是12
>>>
def B(w, v, i, j):
if i == 0:
if w[i] <= j:
return v[i]
else:
return 0
without_i = B(w, v, i - 1, j)
if w[i] > j:
return without_i
else:
with_i = v[i] + B(w, v, i - 1, j - w[i])
return max(without_i, with_i)
if __name__ == "__main__":
w = [2, 3, 4, 5]#list of item's weight
v = [3, 4, 5, 6]#list of item's value
i = len(w) - 1 #number of items
j = 9 #max weight constraints
print (B(w, v, i, j) )
12
>>>
沒有留言:
張貼留言