# 0/1 Knapsack problem
## Problem statement
Ta được cho 1 chiếc balo có thể chứa tối đa trọng lượng là `W`. Ta được cho 1 danh sách đồ vật với lần lượt là cân nặng và giá trị của nó. Nhiệm vụ của ta là làm thế nào để xếp đồ vào ba lô mà giá trị của balo là lớn nhất và trọng lượng không được vượt quá sức chứa tối đa của nó, đồng thời các đồ vật sẽ không được chọn quá 1 lần - Tức là ta chỉ có thể chọn thêm đồ vật `i` vào balo hoặc không cho nó vào balo.
## Approach
1 trong những hướng tiếp cận dễ hiểu và hiệu quả với trường hợp `W` nhỏ đó là sử dụng `Bottom up - Dynamic Programming`. Đây là hướng làm giải các bài toán con cụ thể trước rồi mới xác định bài toán lớn.

Tức là trước khi giải bài toán Knapsack có `W`, ta sẽ tiến hành giải bài toán Knapsack có `W` bé hơn. Sau đó, lưu kết quả vào 1 cấu trúc dữ liệu(ở đây sử dụng sẽ là mảng 2 chiều). Lúc này ta chỉ cần tìm kiếm nghiệm của bài toán lớn trong bảng Bài toán con là được.

## Cách làm?
Như đã nói, ta phải tính toán các bài toán con trước: Ta sẽ tạo 1 cái bảng trông như thế này:

> Bên trái cột 1 là giá trị của 1 đồ vật, cột 1 là cân nặng của nó.
- `Hàng`:
- Hàng đầu tiên: Trọng lượng hay W của balo, ta sẽ giải bài toán con: "Gía trị tối đa có thể xếp vào Balo có W thấp nhất (0) -> W gốc".
- Các hàng còn lại sẽ chứa giá trị lớn nhất thu được nếu balo có giá trị $W_{cột}$.
- `Cột`:
- Cột đầu tiên: chứa `Cân nặng và giá trị` của đồ vật
- Cột còn lại: chứa giá trị lớn nhất có thể khi Balo có W ở cột dóng xuống.

Được rồi, ta sẽ tiến hành duyệt từng hàng từ trên xuống, tại mỗi hàng ta duyệt lần lượt từ trái sang phải.

`Quy tắc`:
- Nếu ta đưa 1 đồ vậy có cân nặng `j`, mà `W - j < 0` thì ta sẽ không đưa j vào. Nhìn vào hình trên. Ta thấy rằng tại `W = 0`, không thể đưa vật 1 vào được nên giá trị lớn nhất ở ô đầu tiên là `0`. Nếu như trong trường hợp balo đã có các đồ vật khác thì số đồ vật trong balo không bị thay đổi.
- Nếu như rơi vào trường hợp còn lại, ta có thể đưa đồ vật hiện tại vào balo, ta sẽ phải lựa chọn xem việc đưa đồ vật hiện tại vào balo hay không đưa nó vào thì tốt hơn. Rồi điền giá trị `max(đưa, không đưa)` vào ô đó.
- Duyệt bảng như vậy thừ đầu đến cuối, và kết quả của ta sẽ nằm ở ô cuối cùng.

## Code up

Dp(W, val, wt){ 
    n = len(wt); 
    //Tiến hành tạo 1 bảng âm trận 2 chiều với W+1 hàng và n + 1 cột 
    dp[n+1][W + 1]; 
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= W; j++){ 
            dp[i][j] = 0; 
        }
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= W; j++){ 
            if(j == 0 || i == 0){
                dp[i][j] = 0; //Nếu W balo hiện tại là 0 hoặc không có đồ vật nào thì mặc định giá trị tối đa bài toán con là 0
            }
            else{ //Nếu không, nếu trọng lượng của độ vật hiện tại không vượt quá sức chứa của balo hiện tại, ta lựa chọn giữa việc đưa nó vào hay không là tốt nhất. 
                pick = 0; 
                if(wt[i - 1] <= j){ //Nếu đưa đồ vật vào, ta lấy giá trị của nó + giá trị tối ưu của bài toán con với W balo - trọng lượng của đồ vật hiện tại không bao gồm đồ vật hiện tại 
                    pick = val[i - 1] + dp[i - 1][j - wt[i - 1]]; 
                }
                not_pick = dp[i - 1][j]; //Nếu không chọn thì chỉ cần lấy giá trị tối ưu của bài toán con khi balo có trọng lượng như hiện tại W, chỉ khác là trường hợp này ta không xét việc có tồn tại đồ vật hiện tại. 
                dp[i][j] = max(pick, not_pick);
            }
        }
    }
    return dp[n][W];
}

## Đánh giá:

Ta cần tạo mảng 2 chiều, và lần lượt điền vào mảng này:
- Time complex: $O(n.W)$
- Space complex: $O(n.W)$

## The Unbouded Knapsack Problem
Ok, nhưng nếu bây giờ thay vì chỉ có thể không chọn hoặc chọn đồ vật với số lượng tối đa là 1, thì lúc này ta có thể chọn 1 đồ vật vô hạn lần, miễn sao balo vẫn còn đủ chỗ để chứa nó.

## Approach
Cũng giống như bài toán Knapsack 0/1, ta sẽ tiến hành giải bài toán con khi `W` nhỏ và `số lượng độ vật` nhỏ hơn bài toán gốc.

Nếu không thể cho đồ vật `i` vào balo thì ta skip nó. Nhưng mấu chốt ở đây khiến cách giải dạng này khác đi 1 chút. Đó là: `"THAY VÌ ĐƯA ĐỒ VẬT HIỆN TẠI VÀO BALO RỒI LẤY GIÁ TRỊ CỦA NÓ CỘNG VỚI GIÁ TRỊ TỐI ƯU NHẤT CỦA BÀI TOÁN CON (GIÁ TRỊ TỐI ƯU NHẤT TẠI W HIỆN TẠI - W ĐỒ VẬT NHƯNG KHÔNG CHỨA GIÁ TRỊ CỦA ĐỒ VẬT LÚC NÀY ĐƯỢC ĐƯA VÀO BALO), TA SẼ LẤY GIÁ TRỊ CỦA NÓ CỘNG VỚI GIÁ TRỊ TỐI ƯU NHẤT CỦA BÀI TOÁN CON(GIÁ TRỊ TỐI ƯU NHẤT TẠI W HIỆN TẠI - W ĐỒ VẬT CÓ THỂ CHỨA GIÁ TRỊ CỦA ĐỒ VẬT LÚC NÀY ĐƯỢC ĐƯA VÀO BALO)"`.

                pick = 0; 
                if(wt[i - 1] <= j){ 
                    pick = val[i - 1] + dp[i][j - wt[i - 1]]; 
                }

-> Đây là dòng duy nhất bị thay đổi, ta sẽ dò giá trị tối ưu nhất trên cùng 1 hàng với W đồ vật hiện tại.

## Code up:

Dp(W, val, wt){ 
    n = len(wt); 
    //Tiến hành tạo 1 bảng âm trận 2 chiều với W+1 hàng và n + 1 cột 
    dp[n+1][W + 1]; 
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= W; j++){ 
            dp[i][j] = 0; 
        }
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= W; j++){ 
            if(j == 0 || i == 0){
                dp[i][j] = 0; //Nếu W balo hiện tại là 0 hoặc không có đồ vật nào thì mặc định giá trị tối đa bài toán con là 0
            }
            else{ //Nếu không, nếu trọng lượng của độ vật hiện tại không vượt quá sức chứa của balo hiện tại, ta lựa chọn giữa việc đưa nó vào hay không là tốt nhất. 
                pick = 0; 
                if(wt[i - 1] <= j){ //Nếu đưa đồ vật vào, ta lấy giá trị của nó + giá trị tối ưu của bài toán con với W balo - trọng lượng của đồ vật hiện tại nhưng lúc này có thể bao gồm trọng lượng của đồ vật hiện tại.
                    pick = val[i - 1] + dp[i][j - wt[i - 1]]; 
                }
                not_pick = dp[i - 1][j]; //Nếu không chọn thì chỉ cần lấy giá trị tối ưu của bài toán con khi balo có trọng lượng như hiện tại W, chỉ khác là trường hợp này ta không xét việc có tồn tại đồ vật hiện tại. 
                dp[i][j] = max(pick, not_pick);
            }
        }
    }
    return dp[n][W];
}

## Đánh giá:
Vì ta làm tương tự cách đầu, nên độ phức tạp thời gian và không gian sẽ vẫn là: $O(n.W)$