Ntucoder – BANHCHUNG – Nấu bánh chưng

1. Nội dung đề bài

• Dữ liệu vào: standard input
• Dữ liệu ra: standard output
• Giới hạn thời gian: 1.0 giây
• Giới hạn bộ nhớ: 128 megabyte

Khác với năm ngoái, năm nay Quý đã lớn nên có thể phụ gia đình gói bánh chưng, vì vậy số lượng bánh chưng năm nay nhiều đến nỗi không thể bỏ hết vào nồi nấu bánh chưng trong một lần được mà phải chia làm nhiều đợt. Nồi bánh chưng nhà Quý có thể tích N (1 <= N <= 50000), nghĩa là có thể chứa tối đa N khối lập phương kích thức 1x1x1 đơn vị. Quý có M (1 <= M <= 5000) cái bánh chưng, bánh chưng thứ i (1 <= i <= M) có thể tích là V_i, tức là bánh chưng này được ghép từ V_i khối lập phương kích thước 1x1x1 đơn vị. Quý muốn biết trong đợt nấu bánh đầu tiên thì có thể xếp tối đa bao nhiêu cái bánh chưng vào nồi. Bạn hãy giúp Quý nhé!

Input

Dòng đầu chứa hai số N, M lần lượt là thể tích nồi bánh chưng và số bánh chưng

M dòng sau, mỗi dòng V_i là thể tích của bánh chưng thứ i

Output

Một dòng duy nhất chứa tổng kích thước bánh chưng tối đa có thể xếp vào nồi trong đợt nấu bánh đầu tiên.

2. Hiểu đề bài như thế nào?

Đề bài kêu chúng ta hãy tìm thể tích lớn nhất từ số lượng bánh chưng đã cho có thể bỏ vào nồi có thể tích cho trước.

3. Cách tui giải và code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int v, n, arr[10000], f[60000] = {0};
    
    /*
    * v: the tich noi banh chung
    * n: so luong banh chung
    * arr: mang luu the tich cac banh chung
    * f: mang danh dau
    */
    
    cin >> v >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    
    
    f[0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = v; j >= arr[i]; --j) {
            if(f[j - arr[i]]){
                f[j] = 1;
            }
        }
    }   
    
    for(int i = v; i >= 0; --i) {
        if(f[i]) {
            cout << i;
            break;
        }
    }
}

Ví dụ:

//input
7 3
2
6
5
//output
7

Như vậy v=7, n=3, arr= {2,6,5}
f là mảng đánh dấu

• Ban đầu:
  

  index	0	1	2	3	4	5	6	7
  value	1	0	0	0	0	0	0	0

• 7 – 2 = 5, 6 – 2 = 4, 5 – 2 =3, 4 – 2 = 2, 3 – 2 = 1:
  Các index 5,4,3,2,1 đều có giá trị 0 nên giá trị index số trừ sẽ giữ nguyên.
  

  index	0	1	2	3	4	5	6	7
  value	1	0	0	0	0	0	0	0

• 2 – 2 =0:
  Còn index 0 có giá trị 1 nên giá trị index của số bị trừ (2) sẽ được thay bằng 1.
  

  index	0	1	2	3	4	5	6	7
  value	1	0	1	0	0	0	0	0

• Tương tự 7 – 6 = 1 và 6 – 6 = 0
  index 0 có giá trị 1 nên giá trị index của số bị trừ (6) sẽ được thay bằng 1.
  

  index	0	1	2	3	4	5	6	7
  value	1	0	1	0	0	0	1	0

• 7 – 5 = 2   index(2) = 1     => index(7) = 1
  6 – 5 = 1  index(1) = 0     => giữ nguyên
  5 – 5 = 0   index(0) = 1     => index(5) = 1
  

  index	0	1	2	3	4	5	6	7
  value	1	0	1	0	0	1	1	1

=> đáp án cuối cùng là index có giá trị 1 cao nhất => index(7) do đó thể tích lớn nhất có thể bỏ vào nồi là 7.

4. Các testcase cho đề bài