題目連結: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';
}