台中女中程式解題系統：b030: 隨選視訊

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b030。
和 b028: 忙碌的超商店員 與 b029: 福袋!福袋!一樣，用 Dynamic Programming 來解。

底下演算法為參考 「演算法筆記的 0/1 Knapsack Problem」 而來的：

程式碼：

1. #include <iostream>  
2. #include <cstring>  
3.   
4. using namespace std;  
5.   
6. int main()  
7. {  
8.     int n, m;  
9.     cin >> n >> m;  
10.   
11.     int v[n], w[m];  
12.   
13.     for(int i = 0; i < n; i++)  
14.     {  
15.         cin >> w[i] >> v[i];  
16.     }  
17.   
18.     int joy[n+1][m+1];  
19.   
20.     memset(joy, 0, sizeof(joy));  
21.   
22.     for (int i = 0; i < n; ++i)     // 窮舉每部影片  
23.     {  
24.          for (int j = 0; j <= m; ++j)// 窮舉每種長度  
25.          {  
26.              if (j - w[i] < 0)  
27.                 // 可觀長度不夠，故只能不看。  
28.                 joy[i+1][j] = joy[i][j];  
29.             else  
30.                 // 可觀長度足夠，可以看或不看。  
31.                 joy[i+1][j] =  
32.                     max(  
33.                         joy[i][j],  
34.                         joy[i][j - w[i]] + v[i]  
35.                     );  
36.          }  
37.     }  
38.   
39.     cout << joy[n][m] << endl;  
40.   
41.     return 0;  
42. }