C++(g++ 7.5.0) 解法, 执行用时: 521ms, 内存消耗: 51908K, 提交时间: 2023-02-14 18:11:47

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

ll t,v;
map<ll,ll>mp;

int main()
{
    ios::sync_with_stdio(0);
    ll n,s;
    cin>>n>>s;
    mp[0]=0;
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        cin>>t>>v;
        for(auto it=mp.rbegin();it!=mp.rend();it++)
        {
            if(it->first+t<=s) mp[it->first+t]=max(mp[it->first+t],mp[it->first]+v);
        }
    }
    for(auto it:mp) ans=max(ans,it.second);
    cout<<ans;
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 470ms, 内存消耗: 51824K, 提交时间: 2023-07-15 12:45:56

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,s,t,v;
map<ll,ll>a;
int main()
{
	cin>>n>>s;
	a[0]=0;
    for(int i=1;i<=n;i++)
    {
    	cin>>t>>v;
    	for(auto it=a.rbegin();it!=a.rend();it++)
    	if(it->first+t<=s)
    	a[it->first+t]=max(a[it->first+t],a[it->first]+v);
	}
	for(auto it:a)
	n=max(n,it.second);
	cout<<n<<endl;
}

Python3 解法, 执行用时: 1603ms, 内存消耗: 99012K, 提交时间: 2023-05-26 16:59:54

import collections

n, s = map(int, input().split())
d = collections.defaultdict(int)
d[0] = 0
res = 0
for _ in range(n):
    t, v = map(int, input().split())
    dt = d.copy()
    for cost, val in dt.items():
        if cost+t<=s:
            d[cost+t] = max(d[cost+t], d[cost]+v)
            res = max(res, d[cost+t])
            
print(res)