Editorial for knap: Ăn trộm thông minh

Hiểu bài toán

Bài toán là bài toán cái túi kinh điển (Knapsack Problem). Cho ~n~ món hàng, mỗi món có trọng lượng ~x~ và giá trị ~y~, và một cái túi có sức chứa tối đa ~M~. Nhiệm vụ là chọn một tập hợp các món hàng sao cho tổng trọng lượng không vượt quá ~M~ và tổng giá trị là lớn nhất có thể.

Các cách tiếp cận

Cách Quy hoạch động 2 chiều (Mảng 2 chiều)

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stdbool.h>
int main(){
    int n,M;
    scanf("%d%d",&n,&M);
    int w[n+1];
    int v[n+1];
    w[0]=0;
    v[0]=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&v[i]);
    }
    int dp[n+1][M+1];
    for(int i=0;i<=n;i++){
        dp[i][0]=0;
    }
    for(int i=0;i<=M;i++){
        dp[0][i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=M;j++){
            if(j<w[i]){
                dp[i][j]=dp[i-1][j];
            }
            else{
                int t=dp[i-1][j-w[i]]+v[i];
                dp[i][j]=(dp[i-1][j]>t)?dp[i-1][j]:t;
            }
        }
    }
    printf("%d",dp[n][M]);
}

• Time Complexity: O(n * M)
• Space Complexity: O(n * M)

Đây là cách tiếp cận trực quan nhất. Ta sử dụng mảng 2 chiều dp[i][j] để lưu tổng giá trị lớn nhất có thể đạt được khi xét i món hàng đầu tiên với sức chứa tối đa là j. Công thức truy hồi:

1. Nếu không chọn món hàng thứ i: dp[i][j] = dp[i-1][j]
2. Nếu chọn món hàng thứ i (chỉ khi j >= w[i]): dp[i][j] = dp[i-1][j - w[i]] + v[i] Giá trị dp[i][j] sẽ là giá trị lớn hơn của 2 trường hợp trên. Cách này dễ hiểu nhưng tốn bộ nhớ.

Cách Quy hoạch động 1 chiều (Tối ưu bộ nhớ)

#include <stdio.h>
#include <string.h>

#define MAX_M 5001

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, M;
    scanf("%d %d", &n, &M);

    int weight[n], value[n];
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &weight[i], &value[i]);
    }

    int dp[MAX_M];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n; i++) {
        for (int j = M; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    printf("%d\n", dp[M]);
    return 0;
}

• Time Complexity: O(n * M)
• Space Complexity: O(M)

Cách này tối ưu bộ nhớ bằng cách dùng mảng 1 chiều dp[j]. Ý tưởng: dp[j] lưu giá trị lớn nhất với sức chứa j. Để tính toán cho món hàng i, ta duyệt j từ M ngược về weight[i]. Việc duyệt ngược đảm bảo rằng ta không sử dụng cùng một món hàng nhiều lần trong cùng một lần cập nhật (tránh trường hợp物品被重复计算). Công thức cập nhật: dp[j] = max(dp[j], dp[j - weight[i]] + value[i]).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán chia thành 2 lựa chọn với mỗi món hàng: hoặc chọn hoặc không chọn.
• Việc tối ưu bộ nhớ từ mảng 2 chiều xuống mảng 1 chiều yêu cầu duyệt vòng lặp sức chứa ngược (từ M về weight[i]) để đảm bảo mỗi món chỉ được dùng 1 lần cho mỗi trạng thái.
• Giới hạn n, M <= 5000 cho phép thuật toán O(n*M) chạy trong thời gian chấp nhận được (~25 triệu thao tác).

Lỗi thường gặp

• Lỗi index: Trong cách 2 chiều, cần chú ý khai báo mảng dp[n+1][M+1] và khởi tạo các giá trị biên (i=0 hoặc j=0) bằng 0.
• Lỗi duyệt vòng lặp: Trong cách 1 chiều, nếu duyệt từ weight[i] đến M (thuận) sẽ导致lỗi chọn trùng món hàng (bốc nhiều lần cùng một món). Phải duyệt ngược từ M về weight[i].
• Overflow: Tổng giá trị có thể lên tới 10000 * 5000 = 50,000,000, nằm trong giới hạn của int (2^31-1), nhưng nếu dùng short hoặc char để tối ưu thì có thể bị tràn số.