C++14(g++5.4) 解法, 执行用时: 14ms, 内存消耗: 512K, 提交时间: 2020-06-20 16:57:30

#include<iostream>
#include<cstring>
using namespace std;
int t;
int n,s;
int main(){
	cin>>t;
	while(t--){
		cin>>n>>s;
		int w[10005],v[10005];
		int dp[10005];
		int ans[10005];
		memset(ans,0,sizeof(ans));
		memset(dp,0,sizeof(dp)); 
		for(int i=1;i<=n;i++){
			cin>>w[i]>>v[i];
		}
		for(int i=1;i<=n;i++){
			for(int j=s;j>=w[i];j--){
				if(dp[j]<dp[j-w[i]]+v[i]){
					dp[j]=dp[j-w[i]]+v[i];
					ans[j]=ans[j-w[i]]+1; 
				}
			}
		} 
		cout<<dp[s]<<" "<<ans[s]<<endl;
	}
}

C++(g++ 7.5.0) 解法, 执行用时: 14ms, 内存消耗: 572K, 提交时间: 2023-05-16 21:54:10

#include<bits/stdc++.h>
using namespace std;
#define N 10005
int t,n,s,w[N],v[N],dp[N],cnt[N];
int main(){
	cin>>t;
	while(t--){
		memset(cnt,0,sizeof(cnt));
		cin>>n>>s;
		for(int i=1;i<=n;i++){
			cin>>w[i]>>v[i];
		}
		for(int i=0;i<=s;i++){
			dp[i]=0;
		}
		for(int i=1;i<=n;i++){
			for(int j=s;j>=w[i];j--){
				if(dp[j]<dp[j-w[i]]+v[i]){
					dp[j]=dp[j-w[i]]+v[i];
					cnt[j]=cnt[j-w[i]]+1;
				}
			}
		}
		cout<<dp[s]<<" "<<cnt[s]<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 12ms, 内存消耗: 792K, 提交时间: 2020-06-22 22:14:37

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

int main()
{
    int i,a,b,n,s,T,DP[10005],num[10005];
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&s);
		memset(DP,0,sizeof(DP)),memset(num,0,sizeof(num));
		while(n--)
		{
			scanf("%d%d",&a,&b);
			for(i=s;i>=a;i--)
			{
				if(DP[i]>=DP[i-a]+b)continue;
				DP[i]=DP[i-a]+b,num[i]=num[i-a]+1;
			}
		}
		printf("%d %d\n",DP[s],num[s]);
	}
}