CAYKHE - Ăn khế trả vàng

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

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


Comments

Please read the guidelines before commenting.



  • 0
    lehongduc  commented on May 15, 2024, 2:21 p.m.

    mặc dù cái này dùng quy hoạch động nhanh hơn nhưng tôn trọng người ra đề nên làm quay lui :)


  • 0
    DIEM10CODER  commented on Feb. 20, 2024, 1:14 p.m.

    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; }


  • 1
    hohoanghai5042011  commented on Feb. 15, 2024, 7:30 a.m.

    #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; }