- #include <iostream>
- #include <cmath>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- int v,n;
- int arr[50];
- int main()
- {
- cin >> v >> n;
- int dp[n+1][v+1];
- for(int i = 1; i <= n; i++)
- cin >> arr[i];
- memset(dp,0,sizeof(dp));
- for(int i = 1; i <= n; i++)
- {
- for(int j = 0; j <= v; j++)
- {
- if(j >= arr[i])
- {
- dp[i][j] = max(dp[i-1][j],dp[i-1][j-arr[i]]+arr[i]);
- }
- else
- {
- dp[i][j] = dp[i-1][j];
- }
- }
- }
- cout << v-dp[n][v] << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2291679.html