Atcoder Educational DP Contest E - Knapsack 2

View as PDF
Submit solution
Points: 0.30 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout
Suggester:
NoobCpp
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ đồ vật được đánh số từ ~1~ đến ~N~. Đồ vật thứ ~i~ ~(1 \le i \le N)~ có khối lượng là ~w_i~ và giá trị là ~v_i~.

Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là ~W~.

Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ ~(1 \le N \le 100)~ và ~W~ ~(1 \le W \le 10^9)~: số lượng đồ vật và sức chứa tối đa của chiếc túi.

~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~w_i~ ~(1 \le w_i \le W)~ và ~v_i~ ~(1 \le v_i \le 10^3)~ lần lượt là khối lượng và giá trị của đồ vật thứ ~i~.

Output

Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Sample 1

Input
3 8
3 30
4 50
5 60
Output
90

Chọn đồ vật ~1~ và ~3~. Tổng khối lượng sẽ là ~3 + 5 = 8~ và tổng giá trị là ~30 + 60 = 90~.

Sample 2

Input
1 1000000000
1000000000 10
Output
10

Sample 3

Input
6 15
6 5
5 6
6 4
6 6
3 5
7 2
Output
17

Chọn đồ vật ~2, 4~ và ~5~. Tổng khối lượng sẽ là ~5 + 6 + 3 = 14~ và tổng giá trị là ~6 + 6 + 5 = 17~.

Comments

Please read the guidelines before commenting.


  • 0
    usingnamespacestd  commented on Oct. 11, 2024, 1:03 a.m.

    value = 1e5


  • 2
    vuthinh1072008  commented on July 21, 2024, 5:28 p.m. ← edited

    code quy hoạch động 2 chiều

    https://ideone.com/EQwRS9


  • 2
    Nguyen_le2632007  commented on May 22, 2024, 12:37 p.m.

    bản chất bài này thì thay vì dùng index và khối lượng để để làm trạng thái thì ta dùng index và giá trị một cách solution dễ đọc dễ hiểu 

    #include <bits/stdc++.h>

using namespace std;
#define mod 1000000007
#define ll long long

ll n, w, a[100009], b[100009];
ll dp[109][100009];

// map&lt;int, map&lt;ll, ll> > dp;

ll dfs(int k, int idx) {
    if (idx == n)
        return (k == 0) ? 0 : INT_MAX;

    if (dp[idx][k] != -1)
        return dp[idx][k];

    if (b[idx] <= k)
        return dp[idx][k] = min(dfs(k, idx + 1), a[idx] + dfs(k - b[idx], idx + 1));
}

int s(int v_max, int min_n) {
    for (int i = v_max; i >= min_n; i--) {
        if (dfs(i, 0) <= w)
            return i;
    }
    return 0;
}

int main() {

    cin >> n >> w;
    memset(dp, -1, sizeof(dp));

    int v_max = 0;
    ll v_min = (int)1e9;

    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        v_max += b[i];
        v_min = min(v_min, b[i]);
    }

    cout << s(v_max, v_min) << endl;
}

  • 0
    RussVN123  commented on March 17, 2024, 9:56 a.m.

    Chắc có mình tui là code mảng 2 chiều :V


    • 0
      melondepchai  commented on June 19, 2024, 4:02 p.m.

      DP như nào vậy ông, tôi làm mãi không xong


      • 3
        RussVN123  commented on June 20, 2024, 4:33 a.m. ← edited

        Spoil nha ông

        ! Thay vì dp[i][j] là giá trị lớn nhất khi xét i vật và khối lượng là j thì mình sẽ đổi thành khối lượng bé nhất khi xét i vật và giá trị là j ( vì giá trị bài này bé ) . Từ đây thì tìm j lớn nhất sao cho f[n][j] <=W thôi ông. Ông có thể xem solution để rõ hơn :VVV


        • 1
          melondepchai  commented on July 7, 2024, 9:38 a.m.

          à ổn r, tks ông nha


  • -13
    phongngutin  commented on Dec. 12, 2023, 1:06 p.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -19
    duonggiabao2008  commented on Dec. 12, 2023, 1:04 p.m. ← edit 2

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -19
    Bui_Quoc_Cuong  commented on Dec. 12, 2023, 1:01 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 3
    beater24  commented on Aug. 20, 2023, 3:36 a.m.

    Đề tuy không khó nhưng phải tối ưu được thời gian tốt


  • -11
    reddevils2709  commented on Feb. 25, 2023, 5:01 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 12
    canhtoanle  commented on May 16, 2022, 8:46 a.m.

    Đề rất hay và bổ ích