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à Vi, tức là bánh chưng này được ghép từ Vi 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 Vi 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.
Đề 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.
#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
=> đá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.
