C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 512K, 提交时间: 2023-08-08 13:12:10

#include<iostream>
#define ll long long
using namespace std;
ll f[20005];
int main()
{
	ll v,n;
	cin>>v>>n;
	for(int i=1;i<=n;i++)
	{
		ll a;
		cin>>a;
		for(int j=v;j>=a;j--)
		f[j]=max(f[j],f[j-a]+a);
	}
	cout<<max((ll)0,v-f[v]);
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2020-03-04 23:42:54

#include<bits/stdc++.h>
using namespace std;
int v,n,i,j,a[101],f[20001];
int main()
{
	cin>>v>>n;
	for(i=1;i<=n;i++)
	cin>>a[i];
	for(i=1;i<=n;i++)
	for(j=v;j>=a[i];j--)
	f[j]=max(f[j],f[j-a[i]]+a[i]);
	cout<<v-f[v];
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 408K, 提交时间: 2020-10-08 08:42:48

#include<bits/stdc++.h>
using namespace std;
int m,n,i,j,a[31],f[20001];
main()
{
	cin>>m>>n;
	for(;i<n;i++)cin>>a[i];
	for(;j<n;j++)
	    for(i=m;i>=a[j];i--)
		    f[i]=max(f[i],f[i-a[j]]+a[j]);
	cout<<m-f[m]; 
}

Python3 解法, 执行用时: 261ms, 内存消耗: 5240K, 提交时间: 2022-07-15 09:17:30

V=int(input())
n=int(input())
dp=[0 for i in range(V+1)]
for i in range(n):
   v=int(input())
   for j in range(V,0,-1):
      if j>=v:
         dp[j]=max(dp[j],(dp[j-v]+v))
print(V-dp[-1])