12/29課程練習

12/29課程練習

If-Then 判斷敘述   巢狀If語法     IF-ElseIf巢狀語法    Select Case語法

課程講義四(1) 　 課程講義四(2) 　 　 　 課程講義四(3)

If-Then 判斷敘述       身高是否合理(P.153)、計算年齡(P.154) 巢狀If語法        世代判斷(P.163)、影片分級(P.164)、判斷閏年(P.166)、 IF-ElseIf巢狀語法        颱風等級(p.176)、BMI計算(p.169) Select Case語法        判斷所屬世代族群及生肖(P.183) 綜合練習(作業)       BMI計算(延伸版)(P.169)       DVD/VCD租借費用(p.155)       判斷是否可進行投票(p.162)、       智力測驗(p.190)、年齡層判斷(p.176)       星座查詢(p.193)、占卜(P.194)

unbounded knapsack problem:

Recall: unbounded knapsack problem

• The unbounded knapsack problem:

http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/knapsack2.html

Problem:

Pack as many items into the knapsack such that the total value of the items packed is maximized     Note: you cannot exceed the capacity of the knapsack !

# Dynamic Programming Python implementation of Coin

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins. The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

Input:

The first line contains an integer 'T' denoting the total number of test cases. In each test cases, the first line contains an integer 'M' denoting the size of array. The second line contains M space-separated integers A1, A2, ..., AN denoting the elements of the array. The third line contains an integer 'N' denoting the cents.

Output:

Print number of possible ways to make change for N cents.

Constraints:

1 ≤ T ≤ 50
1 ≤ N ≤ 300
1 1 ≤ A[i] ≤ 300

Example:

Input:

2
3
1 2 3
4
4
2 5 3 6
10

Output:

4
5

** For More Input/Output Examples Use 'Expected Output' option **

# Dynamic Programming Python implementation of Coin
# Change problem
def count(S, m, n):

# table[i] will be storing the number of solutions for
# value i. We need n+1 rows as the table is constructed
# in bottom up manner using the base case (n = 0)
# Initialize all table values as 0
table = [0 for k in range(n+1)]

# Base case (If given value is 0)
table[0] = 1

# Pick all coins one by one and update the table[] values
# after the index greater than or equal to the value of the
# picked coin
for i in range(0,m):
for j in range(S[i],n+1):
table[j] += table[j-S[i]]

return table[n]

# Driver program to test above function
arr = [1, 2, 3]
m = len(arr)
n = 4
x = count(arr, m, n)
print (x)

# This code is contributed by Afzal Ansari

4
>>>

0/1 背包 完全背包 多重背包

背包問題算是一個蠻經典的演算法問題

這篇主要是以貪婪法來解決此問題，從最高單位價值開始取，取到滿為止

然後每一個物品皆是以可以分割的狀態來處理

 

舉例來說 有5個物品  背包總重w = 50

	Item1	Item2	Item3	Item4	Item5
w重量	10	20	30	10	20
v價值	60	100	120	30	40

 

首先會先計算每個物品的單位價值 v / w

計算後的結果如下

	Item1	Item2	Item3	Item4	Item5
單位價值	6	5	4	3	2

 

接著按照單位價值由小到大排序物品

	Item5	Item4	Item3	Item2	Item1
單位價值	2	3	4	5	6

 

然後從最高價值的開始取，取到剛好滿的重量

Item1 w=10 Item2 = 20  Item3 = 30

取到item3的時候發現背包裝不下，因此把item3切割成剛好的大小

最後的取得方式為 Item1: 1個  Item2: 1個  Item3: 0.667個

取得總價值為 60 * 1 + 100 * 1 + 120*0.667 =240.04

0/1 背包

有n 種不同的物品，每個物品有兩個屬性，size 體積，value 價值，現在給一個容量為 w 的背包，問最多可帶走多少價值的物品。  

完全背包 如果物品不計件數，就是每個物品不只一件的話，稍微改下即可 

01背包

V=10，N=3，c[]={3,4,5}, w={4,5,6}

（1）背包不一定裝滿

      計算順序是：從右往左，自上而下：因為每個物品只能放一次，前面的體積小的會影響體積大的

（2）背包剛好裝滿    

   計算順序是：從右往左，自上而下。注意初始值，其中-inf表示負無窮

完全背包：

V=10，N=3，c[]={3,4,5}, w={4,5,6}

（1）背包不一定裝滿

計算順序是：從左往右，自上而下：  每個物品可以放多次，前面的會影響後面的

（2）背包剛好裝滿

計算順序是：從左往右，自上而下。注意初始值，其中-inf表示負無窮

多重背包：  
多重背包問題要求很簡單，就是每件物品給出確定的件數，求可得到的最大價值  
   多重背包轉換成 01 背包問題就是多了個初始化，把它的件數C 用二進位分解成若干個件數的集合，這裡面數位可以組合成任意小於等於C的件數，而且不會重複，之所以叫二進位分解，是因為這樣分解可以用數位的二進位形式來解釋  
       比如：7的二進位 7 = 111 它可以分解成 001 010 100 這三個數可以組合成任意小於等於7 的數，而且每種組合都會得到不同的數  
       15 = 1111 可分解成 0001  0010  0100  1000 四個數字  
        如果13 = 1101 則分解為 0001 0010 0100 0110 前三個數位可以組合成  7以內任意一個數，即1、2、4可以組合為1——7內所有的數，加上 0110 = 6 可以組合成任意一個大於6 小於等於13的數，比如12，可以讓前面貢獻6且後面也貢獻6就行了。雖然有重複但總是能把 13 以內所有的數都考慮到了，基於這種思想去把多件物品轉換為，多種一件物品，就可用01 背包求解了。  

 copy

1.  int n;  //輸入有多少種物品  

2.  int c;  //每種物品有多少件  

3.  int v;  //每種物品的價值  

4.  int s;  //每種物品的尺寸  

5.  int count = 0; //分解後可得到多少種物品  

6.  int value[MAX]; //用來保存分解後的物品價值  

7.  int size[MAX];  //用來保存分解後物品體積  

8.    

9.  scanf("%d", &n);    //先輸入有多少種物品，接下來對每種物品進行分解  

10.  

11.while (n--)     //接下來輸入n中這個物品  

12.{  

13.    scanf("%d%d%d", &c, &s, &v);  //輸入每種物品的數目和價值  

14.    for (int k=1; k<=c; k<<=1)   //<<右移 相當於乘二  

15.    {  

16.        value[count] = k*v;  

17.        size[count++] = k*s;  

18.        c -= k;  

19.    }  

20.    if (c > 0)  

21.    {  

22.        value[count] = c*v;  

23.        size[count++] = c*s;  

24.    }  

25.}  

定理：一個正整數n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是滿足n-2^k+1>0的最大整數）的形式，且1～n之內的所有整數均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某幾個數的和的形式。

證明如下：

（1） 數列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和為n，所以若干元素的和的範圍為：[1, n]；

（2）如果正整數t<= 2^k – 1,則t一定能用1,2,4,…,2^(k-1)中某幾個數的和表示，這個很容易證明：我們把t的二進位表示寫出來，很明顯，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二進位數字為0或者1.

（3）如果t>=2^k,設s=n-2^k+1，則t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某幾個數的和的形式，進而t可以表示成1,2,4,…,2^(k-1)，s中某幾個數的和（加數中一定含有s）的形式。

（證畢！）

來源
http://www.csie.ntnu.edu.tw/~u91029/KnapsackProblem.html

Unbounded Knapsack Problem

無限背包問題

物品有許多種類，每一種物品都無限量供應的背包問題。

UVa 10465

演算法

分割問題的方式可以仿照 0/1 背包問題。 0/1 背包問題是一個物品的去留；無限背包問題則是一種物品的去留。考慮一種物品的各種用量：

c(n, w) = max(
   c(n-1, w - weight[n] ⋅ 0) + cost[n]     ,   用去零個第n種物品
   c(n-1, w - weight[n] ⋅ 1) + cost[n] ⋅ 1 ,   用去一個第n種物品
   c(n-1, w - weight[n] ⋅ 2) + cost[n] ⋅ 2 ,   用去兩個第n種物品
   ... ,                                       ...
)

n：第0種到第n種物品要放進背包內。
w：背包耐重限制。
c(n, w)：只有第0種到第n種物品，耐重限制為w，此時的背包問題答案。
weight[n]：第n種物品的重量。
cost[n]：第n種物品的價值。

VB2010 12/29 日 練習題

課程講義四(1)

　

課程講義四(2)

課程講義四(3)

If-Then 判斷敘述

      身高是否合理(P.153)、計算年齡(P.154)

巢狀If語法

       世代判斷(P.163)、影片分級(P.164)、判斷閏年(P.166)、

IF-ElseIf巢狀語法

       颱風等級(p.176)、BMI計算(p.169)

Select Case語法

       判斷所屬世代族群及生肖(P.183)

綜合練習(作業)

      BMI計算(延伸版)(P.169)

      DVD/VCD租借費用(p.155)

      判斷是否可進行投票(p.162)、

      智力測驗(p.190)、年齡層判斷(p.176)

      星座查詢(p.193)、占卜(P.194)

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

>>>