C++ 解法, 执行用时: 5ms, 内存消耗: 416KB, 提交时间: 2022-08-06

#include<iostream>
#include<vector>
#include<limits.h>
#include<algorithm>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	vector<int> ans(n,0);
	for(int i=0;i<n;i++)
	cin>>ans[i];
	sort(ans.begin(),ans.end());
	vector<int> dp(m+1,INT_MAX);
	dp[0]=0;
	for(int i=n-1;i>=0;i--)
	{
		for(int j=ans[i];j<=m;j++)
		dp[j]=min(dp[j-ans[i]]+1,dp[j]);
	 } 
	if(dp[m]==INT_MAX)
	cout<<-1;
	else
	cout<<dp[m];
}

C++ 解法, 执行用时: 5ms, 内存消耗: 416KB, 提交时间: 2022-07-27

#include<iostream>
#include<vector>
#include<limits.h>
#include<algorithm>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> ans(n,0);
    for(int i=0;i<n;i++)
        cin>>ans[i];
    sort(ans.begin(),ans.end());
    //for(int i=0;i<n;i++)
    //    cout<<ans[i];
    vector<int> dp(m+1,INT_MAX);
    dp[0]=0;
    for(int i=n-1;i>=0;i--)
    {
        for(int j=ans[i];j<=m;j++)
            dp[j]=min(dp[j-ans[i]]+1,dp[j]);
    }
    if(dp[m]==INT_MAX) cout<<-1;
    else cout<<dp[m];
}

C++ 解法, 执行用时: 5ms, 内存消耗: 416KB, 提交时间: 2022-04-16

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include <cmath>
using namespace std;
int main()
{
    int n, aim;
    cin >> n >> aim;
    vector<int> dp2(aim + 1, 5000);
    dp2[0] = 0;
    vector<int> num(n);
    for(auto &i : num)
    {
        cin >> i;
    }
    for (int j = 0; j < n; j++)
    {
        for (int i = num[j]; i <= aim; i++)
        {
            dp2[i] = min(dp2[i], dp2[i - num[j]] + 1);
        }
    }
    cout << (dp2[aim] >= 5000 ? -1 : dp2[aim]) << endl;

}

C++ 解法, 执行用时: 5ms, 内存消耗: 428KB, 提交时间: 2022-05-08

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

int main(){
    int n, aim, x;
    cin >> n >> aim;
    int dp[aim + 1];
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for(int i = 0; i < n; i ++){
        cin >> x;
        for(int j = x; j <= aim; j ++){
            dp[j] = min(dp[j], dp[j - x] + 1);
        }
    }
    if(dp[aim] == 0x3f3f3f3f) cout<<-1;
    else cout<<dp[aim];
    return 0;
}

C 解法, 执行用时: 5ms, 内存消耗: 432KB, 提交时间: 2022-05-25

#include<stdio.h>

int min(int a,int b){
	if(a>=b) return b;
	else return a;
}

int main(){
	int n,aim;
	scanf("%d %d",&n,&aim);
	int a[aim+1],b[n+1];
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	a[0]=0;
	for(int i=1;i<=aim;i++){
		a[i]=5001;
	}
	for(int i=1;i<=n;i++){
		for(int j=b[i];j<=aim;j++){
			a[j]=min(a[j],a[j-b[i]]+1);
		}
	}
	if(a[aim]==5001) printf("-1");
	else printf("%d",a[aim]);
	
	return 0;
}