本质是一个背包问题,只不过质量最大条件转化为了体积最大
所以两维都是体积
#include<iostream>
using namespace std;
const int N=1e5;
int v[N],f[N];
int main()
{
int V,n;
cin>>V>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
for(int i=1;i<=n;i++)
{
for(int j=V;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+v[i]);
}
}
cout<<V-f[V];
}