C++ 解法, 执行用时: 4ms, 内存消耗: 552K, 提交时间: 2022-01-10 19:17:32

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int dp[51000],v[51000],w[51000];

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&v[i],&w[i]);
	}
	memset(dp,INF,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(j>=v[i]){
				dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
			}else{
				dp[j]=min(dp[j],w[i]);
			}
		}
	}
	printf("%d\n",dp[m]);
} 

Python3 解法, 执行用时: 608ms, 内存消耗: 6000K, 提交时间: 2022-10-03 20:46:59

a=[0 for i in range(50005)]
n,h=map(int,input().split())
ans=99999999
for j in range(n):
    q,t=map(int,input().split())
    s=1
    while 1:
        if s>=t:
            a[s]=max(a[s],a[s-t]+q)
        if a[s]>=h:
            ans=min(s,ans)
            break
        s+=1
print(ans)