b030: 隨選視訊. FYI: https://yunlinsong.blogspot.com/2019/11/b030.html

b030.cpp

#include <iostream>  
#include <cstring>  
  
using namespace std;  
  
int main()  
{  
    int n, m;  
    cin >> n >> m;  
  
    int v[n], w[m];  
  
    for(int i = 0; i < n; i++)  
    {  
        cin >> w[i] >> v[i];  
    }  
  
    int joy[n+1][m+1];  
  
    memset(joy, 0, sizeof(joy));  
  
    for (int i = 0; i < n; ++i)     // 窮舉每部影片  
    {  
         for (int j = 0; j <= m; ++j)// 窮舉每種長度  
         {  
             if (j - w[i] < 0)  
                // 可觀長度不夠，故只能不看。  
                joy[i+1][j] = joy[i][j];  
            else  
                // 可觀長度足夠，可以看或不看。  
                joy[i+1][j] =  
                    max(  
                        joy[i][j],  
                        joy[i][j - w[i]] + v[i]  
                    );  
         }  
    }  
  
    cout << joy[n][m] << endl;  
  
    return 0;  
}