Discription
小Ho現在手上有M張獎券,而獎品區有N件獎品,分别标号為1到N,其中第i件獎品需要need(i)張獎券進行兌換,同時也隻能兌換一次,為了使得辛苦得到的獎券不白白浪費,小Ho給每件獎品都評了分,其中第i件獎品的評分值為value(i),表示他對這件獎品的喜好值。現在他想知道,憑借他手上的這些獎券,可以換到哪些獎品,使得這些獎品的喜好值之和能夠最大。
每組測試資料的第一行為兩個正整數N和M,表示獎品的個數,以及小Ho手中的獎券數。
接下來的n行描述每一行描述一個獎品,其中第i行為兩個整數need(i)和value(i),意義如前文所述。
Solution
int main()
{
int N, M;
cin >> N >> M;
int x, y;
vector<int> need, value;
for (int i = 0; i < N; i++){
cin >> x >> y;
need.push_back(x);
value.push_back(y);
}
vector<int> dp(M+1,0);
for (int i = 0; i <N; i++){
for (int j = M; j>need[i]; j--){
dp[j] = max(dp[j], dp[j - need[i]] + value[i]);
}
}
cout << dp[M] << endl;
cin.get();
cin.get();
return 0;
}
Discription
每個獎品可以兌換無數次
Solution
int main()
{
int N, M;
cin >> N >> M;
int x, y;
vector<int> need, value;
for (int i = 0; i < N; i++){
cin >> x >> y;
need.push_back(x);
value.push_back(y);
}
vector<int> dp(M+1,0);
for (int i = 0; i <N; i++){
for (int j = 0; j<=M; j++){
if (need[i] <= j){
dp[j] = max(dp[j], dp[j - need[i]] + value[i]);
}
}
}
cout << dp[M] << endl;
cin.get();
cin.get();
return 0;
}
GitHub-Leetcode: https://github.com/wenwu313/LeetCode