Cái túi 1

Xem dạng PDF
Gửi bài giải
Điểm: 0,42 (OI)
Giới hạn thời gian: 0.9s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cây khế nhà Khánh rất sai quả nên có một con chim to to đến ăn. Ăn xong, chim chở Khánh ra đảo để trả công bằng vàng. Đảo có ~N~ cục vàng. Anh ấy muốn chuyển hết cả ~N~ cục vàng của mình về nhà. Nhưng khổ nổi các cục vàng này lại có trọng lượng và kích thước khổng lồ. Khánh đem theo một cái túi ba trăm gang to đùng nhưng vẫn chưa chắc chứa hết đống vàng này. Khổ quá đi! Lấy cục nào, bỏ cục nào bây giờ! Các bạn giúp anh ấy tìm ra một cách chọn vàng để thu được giá trị lớn nhất mà vẫn không làm rách túi đi.

Input

  • Dòng ~1~: Chứa ~2~ số nguyên: số cục vàng ~N~ ~\left(1 \leq N \leq 40\right)~ và tải trọng tối đa của túi ~M~ ~\left(1 \leq M \leq 10^9\right)~.
  • ~N~ dòng sau: Mỗi dòng chứa ~2~ số nguyên: trọng lượng ~W_{i}~ và giá trị ~V_{i}~ của cục vàng thứ ~i~ ~\left(1 \leq W_{i}, V_{i} \leq 10^8\right)~.

Output

  • Một số nguyên duy nhất là giá trị lớn nhất thu được.

Sample Input

3 4
1 4
2 5
3 6

Sample Output

10

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    vuonghoaitamdz9  đã bình luận lúc 9, Tháng 12, 2025, 16:08 ← chỉnh sửa

    Spoil

    MITM kết hợp lọc phần tử

    Code mẫu : https://ideone.com/iNWb4e


  • 0
    ngoccaidu2008  đã bình luận lúc 31, Tháng 10, 2025, 22:27

    code đứng top 2 tham khảo nhé:

    #include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define __Hormer_Nguyen__ signed main()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
const int MOD=1000000007;
const int maxn=5+1e6;
int n,m;
int ans=-15032008;
struct v
{
    int w,v;
}a[maxn];
vector<pair<int,int>>B;
vector<int>wa;
vector<int>va;
vector<int>wb;
vector<int>vb;
void bta(int i,int sw,int v)
{
    if (sw>m) return;
    if (i>n/2)
    {
        wa.push_back(sw);
        va.push_back(v);
        return;
    }bta(i+1,sw,v);
    bta(i+1,sw+a[i].w,v+a[i].v);
}
void btb(int i,int sw,int v)
{
    if (sw>m) return;
    if (i>n)
    {
        B.push_back({sw,v});
        return;
    }btb(i+1,sw,v);
    btb(i+1,sw+a[i].w,v+a[i].v);
}
__Hormer_Nguyen__
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //jd();
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>a[i].w>>a[i].v;

    bta(1,0,0);
    btb(n/2+1,0,0);

    sort(B.begin(),B.end());
    int ma=-1;
    for (auto i:B)
    {
        if (i.second>ma)
        {
            wb.push_back(i.first);
            vb.push_back(i.second);
            ma=i.second;
        }
    }
    for (int i=0;i<wa.size();i++)
    {
        int k=upper_bound(wb.begin(),wb.end(),m-wa[i])-wb.begin()-1;
        ans=max(ans,va[i]+vb[k]);
    }cout<<ans;
}

  • -3
    haiduong151109  đã bình luận lúc 2, Tháng 10, 2025, 2:33

    hi ae


  • -1
    hmtphong7749  đã bình luận lúc 14, Tháng 2, 2025, 13:58

    sao cứ đúng được 9 đầu xong lại sai nhỉ


    • -1
      minhkochamhoc  đã bình luận lúc 7, Tháng 6, 2025, 13:01

      dạng này là dạng chia đôi tập nhé bạn , bạn nhìn điều kiện sẽ thấy nó ko thể lập mảng 2 chiều rồi dp được , muốn làm dạng này trước tiên bạn đọc phần chia đôi tập trên vnoi wiki nhé


      • 0
        nguyenngocthanhhai  đã bình luận lúc 15, Tháng 9, 2025, 10:02

        được ác luôn ấy chứ, thuật chuẩn phải dp 2 chiều


        • -3
          MnhatBeo  đã bình luận lúc 6, Tháng 12, 2025, 8:31

          gpt nộp lần đầu 0.34s lần 2 0.56s thì im mồm


  • -1
    mickey21082013  đã bình luận lúc 7, Tháng 12, 2024, 14:27

    hi hi


    • -1
      quangvukts  đã bình luận lúc 31, Tháng 8, 2025, 9:49

      .


  • -1
    phancuongtmtlhp  đã bình luận lúc 20, Tháng 11, 2024, 5:12

    Ai đó cho mình xin ý tưởng bài này vs! em đọc sol mà không có hiểu


  • -8
    tienthinh081  đã bình luận lúc 31, Tháng 8, 2024, 1:29

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -1
    dongquan247  đã bình luận lúc 7, Tháng 8, 2024, 22:55 ← chỉnh sửa

    bị sai test case cuối :(


  • -27
    TBThao  đã bình luận lúc 23, Tháng 11, 2023, 5:33

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 62
    I_love_Hoang_Yen  đã bình luận lúc 20, Tháng 8, 2021, 3:32 ← chỉnh sửa

    Mình vừa cập nhật bộ test bài này và rejudge (cảm ơn bạn kazamahoang đã đóng góp test). 1 số bạn đã mất AC.

    Ngoài ra bộ test bài này không phù hợp để chấm kiểu OI, nên mình đã đổi sang chấm kiểu ICPC.