P1049 [noip2001 popularization group t4] packing problem

【 Title source 】
https://www.luogu.com.cn/problem/P1049
https://www.acwing.com/problem/content/1026/

【 Title Description 】
There is a box with the capacity of V, At the same time there is n Items , Each object has a volume （ Positive integer ）.
requirement n An object in , Take any number of them and put them in the box , Make the box's Remaining space by Minimum .

【 Input format 】
The first line is an integer V, Indicates the capacity of the box .
The second line is an integer n, It means the number of items .
Next n That's ok , One positive integer per line （ No more than 10000）, It means that n The volume of each object .

【 Output format 】
An integer , Represents the remaining space in the box .

【 Data range 】
0<V≤20000,0<n≤30

【 Algorithm code 】

#include <bits/stdc++.h>
using namespace std;

const int maxv=20005,maxn=35;
int v[maxn];
int f[maxn][maxv];
//f[i][j]: The previous i items which total volume does not exceed j

int main() {
	int vx,n;
	cin>>vx>>n;
	for(int i=1; i<=n; i++) cin>>v[i];

	for(int i=1; i<=n; i++) {
		for(int j=1; j<=vx; j++) {
			f[i][j]=f[i-1][j]; //Don't select current item
			if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+v[i]);
			//Select the current item and the volume must be sufficient
		}
	}
	cout<<vx-f[n][vx]<<endl; //Free space

	return 0;
}

/*
in:
24
6
8
3
12
7
9
7

out:
0
*/

【 reference 】
https://www.acwing.com/solution/content/91279/