C++14(g++5.4) 解法, 执行用时: 19ms, 内存消耗: 724K, 提交时间: 2019-08-30 14:01:10

#include<iostream>
#include<algorithm>
using namespace std;

int h, n, a, dp[45005];

int main() {
	cin >> h >> n;
	for(int i = 0; i < n; i++) {
		cin >> a;
		for(int j = a; j <= h; j++) dp[j] = max(dp[j], dp[j-a]+a);
	}
	cout << dp[h] << endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 23ms, 内存消耗: 508K, 提交时间: 2019-08-30 12:34:01

#include<bits/stdc++.h>
using namespace std;
int a[510],dp[45010];
int main(){
	int n,m;
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	for(int j=m;j>=a[i];j--)
	dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
	cout<<dp[m]<<"\n";
	return 0;
}

Pascal(fpc 3.0.2) 解法, 执行用时: 22ms, 内存消耗: 376K, 提交时间: 2019-08-30 08:15:17

var m,n,i,j:longint;
    w,f:array[1..50000]of longint;
begin
  readln(m,n);
  for i:=1 to n do
    readln(w[i]);
  for i:=1 to n do
    for j:=m downto w[i] do
      if f[j]<f[j-w[i]]+w[i] then f[j]:=f[j-w[i]]+w[i];
  write(f[m]);
end.

pypy3(pypy3.6.1) 解法, 执行用时: 132ms, 内存消耗: 20336K, 提交时间: 2021-05-03 21:09:16

N=[]
H=[0]*46000
h,n=map(int,input().split())
for i in range(n):
    N.append(int(input()))
for i in range(n):
    for j in range(h,N[i]-1,-1):
        H[j]=max(H[j],H[j-N[i]]+N[i])
print(H[h])