【題解】Green Judge b030: 隨選視訊

題目連結：http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b030

解法：背包問題

#include <iostream>
#include <cstring>
using namespace std;
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m; //n=總影片數，m=小綠可以觀賞的影片總長度
    int w[n+1], v[n+1];
    for(int i=1; i<=n; i++)
        cin >> w[i] >> v[i]; //第i部影片有w[i]分鐘，滿足度為v[i]
    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=n; i++){ //考慮看第i部影片的時候
        for(int j=1; j<=m; j++){ //最多只能看j分鐘
            if(j - w[i] < 0){ //長度不夠看第i部影片，故只能不看
                dp[i][j] = dp[i-1][j]; //不看的話，等於只看了i-1部且仍可看j分鐘
            }else{ //長度足夠，可以看或不看(選最大價值)
                dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]); //如果看的話，答案等於看了i-1部，再加上這一部的價值，且剩下j-w[i]分鐘
            }
        }
    }
    cout << dp[n][m] << '\n';
}