C++ 解法, 执行用时: 8ms, 内存消耗: 432K, 提交时间: 2021-06-18 21:32:51

#include<bits/stdc++.h>
using namespace std;
int n,k,dp[10005];
struct node{
	int a,b;
}x[1005];
bool cmp(node q,node p){
	return q.a-q.b<p.a-p.b;
}
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d %d",&x[i].a,&x[i].b);
	sort(x+1,x+1+n,cmp);
	for(int i=1;i<=n;i++)
		for(int j=k;j>=x[i].a;j--)
			dp[j]=max(dp[j],dp[j-x[i].b]+x[i].b);
	printf("%d",k-dp[k]);
	return 0;
}

Python3 解法, 执行用时: 1572ms, 内存消耗: 4808K, 提交时间: 2022-10-26 11:19:09

n, k = (map(int, input().split()))
arr = []
for i in range(n):
    arr.append( tuple(map(int, input().split())) )

arr.sort(key=lambda x: x[0] - x[1], reverse=True)

f = [0 for _ in range(10005)]
f[k] = 1
for i in range(n):
    for j in range(arr[i][0], k + 1):
        f[j-arr[i][1]] |= f[j]
res  = 1
while not f[res]:
    res+=1
print(res)

pypy3 解法, 执行用时: 125ms, 内存消耗: 20840K, 提交时间: 2021-06-20 10:19:58

n, k = (map(int, input().split()))
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

arr.sort(key=lambda x: x[0] - x[1], reverse=True)

f = [0] * 100005
f[k] = 1
for i in range(n):
    for j in range(arr[i][0], k + 1):
        f[j-arr[i][1]] |= f[j]
res  = 1
while not f[res]:res+=1
print(res)