Hướng dẫn giải của Atcoder Educational DP Contest D - Knapsack 1

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: NoobCpp

Đây là bài toán quy hoạch động cái túi cơ bản. Lưu ý rằng vì ~v_i \le 10^9~, ta không thể lưu ~v_i~ trong mảng ~dp~ của mình. Thay vào đó, có thể lưu khối lượng ~W~ ~(W \le 10^5)~. Gọi ~dp[i][j]~ là tổng giá trị lớn nhất có thể khi xét ~i~ đồ vật đầu tiên và có tổng khối lượng là ~j~. Bài toán trở về quy hoạch động cái túi cơ bản.

Độ phức tạp thuật toán: ~O(N \cdot W)~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int mx = 1e5+1;

template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}

long long dp[101][mx];
int w[101], v[101];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N, W; cin >> N >> W;
    for(int i = 0; i < N; ++i) cin >> w[i] >> v[i];

    for(int i = 0; i < N; ++i) for(int j = 0; j <= W; ++j) {
        if(j + w[i] <= W) ckmax(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
        ckmax(dp[i + 1][j], dp[i][j]);
    }

    cout << dp[N][W] << endl;
}

Bình luận

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

ducquoc đã bình luận lúc 13, Tháng 1, 2025, 12:27 ← chỉnh sửa →

Ý tưởng: dùng mảng 2 chiều dp[N+1][W+1] để lưu memo trạng thái chọn tối đa món thứ i (N), giới hạn trọng lượng j (W), quy hoạch động (lặp).

Nếu vật thứ i không được chọn vào phương án tối ưu, thì kết quả tối ưu sẽ được chọn trong (i−1) đồ vật trước đó với giới hạn trọng lượng vẫn là j.
Nếu vật thứ i được chọn vào phương án tối ưu, thì tải trọng còn lại có thể sử dụng là (j−w[i]) cho (i−1) đồ vật phía trước, và ta được thêm giá trị v[i] của vật thứ i. Dĩ nhiên, trường hợp này chỉ xét đến khi j >= w[i].

dp[i][j]= { dp[i−1][j] }                                   , khi j < w[i]
dp[i][j]= max{ dp[i−1][j], dp[i-1][j - w[i-1]] + v[i - 1] }, khi j >= w[i]

Kết quả của bài toán chính là dp[N][W]. (Cũng có thể chỉ cần mảng 1 chiều dp[W+1], nếu nắm được chỉ số v[i] và w[i] tương ứng 1-index hoặc [i-1] tương ứng 0-index, kết quả là dp[W]).

Knapsack bằng lặp (iterative) thì trực quan hơn đệ quy (recursive), implementation sample như sau:

https://oj.vnoi.info/src/8165589

import java.io.*; import java.util.*;

// code mẫu của `ducquoc`

@SuppressWarnings("all") // https://oj.vnoi.info/problem/atcoder_dp_d
class VoAtcoderDpD {
    public static void sol(PrintStream os) {
        QDS in = new QDS(); PrintWriter out = new PrintWriter(os);
        int N = in.nextInt(), W = in.nextInt(); int v[] = new int[N], w[] = new int[N];
        for (int i = 0; i < N; i++) { w[i] = in.nextInt(); v[i] = in.nextInt(); }
        out.println(knapsackMaxVal(W, w, v, N)); out.close(); in.close();
    }

    static long knapsackMaxVal(int W, int[] w, int[] v, int N) {
        long dp[][] = new long[N + 1][W + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= W; ++j) {
                dp[i][j] = dp[i - 1][j]; // skip
                if (j >= w[i - 1]) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); // take
            }
        }
        return dp[N][W];
    }

    final public static void main(String[] args) throws Exception { //System.setOut(new PrintStream("O.out");
        System.setIn(new ByteArrayInputStream("3 8\n3 30\n4 50\n5 60".getBytes())); //FileInputStream("I.inp"));
        sol(System.out);
    }
}
/** quick data Scanner */
class QDS {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 4096); StringTokenizer st;
    public String next() { while (st == null || !st.hasMoreTokens()) { try { st = new StringTokenizer(
            br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); }
    public int nextInt() { return Integer.parseInt(next()); }
    public void close() { if (br != null) { try { br.close(); } catch (IOException e) { e.printStackTrace(); } } }
}

-44

tuan1 đã bình luận lúc 3, Tháng 3, 2022, 2:21

mn cho hỏi sao code này của e bị RE thế ạ

include<bits/stdc++.h>

using namespace std; long long dp[101][10001]; int W,w[101],v[101],n; int main() {
iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); cin>>n; cin>>W; for(int i=1;i<=n;i++) { cin>>w[i]; cin>>v[i]; } long long s=0; dp[0][0]=0; for(int i=1;i<=n;i++) { if(s<W)s+=w[i]; for(int j=0;j<=s;j++) { dp[i][j]=dp[i-1][j]; if(w[i]<=j){dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);} } } cout<<dp[n][W]; }

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