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

1. Đề bài BANHCHUNG – Nấu bánh chưng

Link: http://laptrinh.ntu.edu.vn/Problem/Details/5518

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.

Ví dụ

input

7 3
2
6
5

output

7

Giải thích ví dụ

Ta sẽ bỏ bánh chưng thứ nhất và thứ ba vào nồi, vậy tổng kích thước của bánh chưng trong nồi là 2 + 5 = 7

2. Hướng dẫn giải bài

ý tưởng bài này tương tự như bài chia kẹo.

Ta sẽ xây dựng các tổng có thể lập đk từ các thể tích của những chiếc bán chưng.ta gọi f[i]=1 tức tổng i có thể lập và ngược lại;

ta duyệt lần lượt từng phần tử a[i]:nếu f[j-a[i]]=1 thì f[j]=1;

sau đó dê dàng tìm ra thể tích bánh chưng chồng đk nhất.

để chương trình chạy nhanh hơn 1 chút,ta có thể dung một mảng s để đánh dấu với ý nghĩa s[i]=p tức tổng p có thể lập đk.sau đó duyệt từng phần tử a[i],với mỗi a[i] ta sẽ lập được tổng s[j]+a[i].nếu s[j]+a[i]<=n vào s[j]+a[i] chưa có trong s thì ta them vào mảng s;

3. Code BANHCHUNG NTU

#include <bits/stdc++.h>

using namespace std;
int n,m;
int a[100001];
void doc()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i];
}
int f[100001],s[100001];
void tinh()
{
    sort(a+1,a+m+1);
    int sl=m;
    for(int i=1;i<=m;i++) if(a[i]>n) sl--;
    m=sl;
    f[0]=1;
    int sn=1;
    s[sn]=0;
    for(int i=1;i<=m;i++)
    {
        int sl=sn;
        for(int j=sl;j>=1;j--)
        if(f[s[j]+a[i]]==0&&s[j]+a[i]<=n)
        {
            f[s[j]+a[i]]=1;
            s[++sn]=s[j]+a[i];
        }
    }

    for(int i=n;i>=0;i--)
        if(f[i]==1)
    {
        cout<<i;
        return;
    }
}

int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    doc();
    tinh();
}