b030: 隨選視訊

b030: 隨選視訊

小綠購買了某線上影視公司提供的隨選視訊方案，只要付一筆費用，就可以觀看總長度 M 分鐘的影片，小綠從該公司提供的影片中挑選了 N 部有興趣的電影，每部電影都有不同的長度以及滿足感，請問你小綠該如何選擇，才能得到最大的滿足感。挑選影片的限制如下：

1. 影片一定要從頭看到尾，只看一半得不到任何的滿足感。 
2. 同一部影片只需要看一次，看兩次以上滿足感並不會增加。
3. 影片的觀賞順序並不會影響它們的滿足感。

輸入說明：

第一行有兩個正整數 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)  )

======== RESTART: F:/Python_APSC/b031-1.py =====================
12

>>>