台中女中程式解題系統: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. }  

沒有留言: