CAYKHE - Ăn khế trả vàng
Xem dạng PDF
Hẳn chúng ta ai cùng biết câu truyện cổ tích Cây Khế (hay là câu truyện ăn khế trả vàng). Ở đoạn kết của câu truyện, khi người em mang theo túi ba trăm gang được chim chở ra đảo vàng, người em vô cùng lúng túng không biết làm sao để chọn được những thỏi vàng cho vừa túi mà tổng giá trị lớn nhất, lấy thỏi nào, bỏ thỏi nào, vấn đề phức tạp đây. Em hãy viết chương trình giúp người em nhanh chóng lựa chọn vàng để chim chở về chứ cứ ở ngoài đảo lâu mà gặp bão to thì nguy.
Cho biết cái túi đựng được tối đa là ~M~ kg vàng và trên đảo có ~N~ thỏi vàng, thỏi thứ ~i~ có khối lượng ~w_i~ và giá trị ~v_i~. Hãy xác định giá trị lớn nhất của số vàng mà túi đựng được (không vượt quá trọng lượng tối đa của túi có thể đựng được).
Input
- Dòng đầu là hai số ~N, M~ lần lượt là số thỏi vàng trên đảo và tải trọng tối đa của túi;
- ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương là trọng lượng và giá trị của thỏi vàng thứ ~i~.
Giới hạn:
- Trong tất cả các test có: ~1 ≤ M, w_i, v_i ≤ 10^4~.
- ~40\%~ số test (ứng với ~40\%~ số điểm của bài) có ~1 ≤ N ≤ 10~;
- ~40\%~ số test khác (ứng với ~40\%~ số điểm của bài) có ~10 < N ≤ 20~;
- ~20\%~ số test còn lại (ứng với ~20\%~ số điểm của bài) có ~20 < N ≤ 40~.
Output
- Gồm một dòng duy nhất ghi số nguyên không âm là đáp số bài toán.
Sample
Input #1
3 4
1 4
2 5
3 6
Output #1
10
Hint
- Ta chọn thỏi vàng thứ ~1~ và thứ ~3~ thì trổng trọng lượng là ~4~ và tổng giá trị là ~10~.
Problem source: Chuyên Sơn La Online Judge
Bình luận
include <bits/stdc++.h>
using namespace std; int dp[50][40010],n,S,W[41],V[41]; vector<int> ans ; int main(){ cin >> n >> S; for(int i=1;i<=n;i++){ cin >> W[i]>> V[i]; } for(int i=1;i<=n;i++){ for(int j=0;j<=S;j++){ if(j==0||i==0){ dp[i][j]=0; } if(j<W[i]){ dp[i][j]=dp[i-1][j]; } else{ dp[i][j]=max(dp[i-1][j],V[i]+dp[i-1][j-W[i]]); } ans.push_back(dp[i][j]); } } sort(ans.begin(),ans.end(),greater<int>()); cout << ans[0]; return 0; }
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; struct Gold { int weight; int value; }; int knapsack(int capacity, vector<Gold>& golds) { int n = golds.size(); vector dp(n + 1, vector<int>(capacity + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int w = 1; w <= capacity; ++w) {
if (golds[i - 1].weight > w) {
dp[i][w] = dp[i - 1][w];
} else {
dp[i][w] = max(dp[i - 1][w], golds[i - 1].value + dp[i - 1][w - golds[i - 1].weight]);
}
}
}
return dp[n][capacity];
}
int main() {
int N, M;
cin >> N >> M;
vector<Gold> golds(N);
for (int i = 0; i < N; ++i) {
cin >> golds[i].weight >> golds[i].value;
}
int result = knapsack(M, golds);
cout << result << endl;
return 0;
}