题目链接

动态规划维护价值大于p下的接口最小值

#include<bits/stdc++.h>
using namespace std ;
const int Max = 1e3 + 10 ; 
int f[Max] , g[Max] ;
// f:价值
// g:接口大小 
struct Node {
	int w , v ; 
} Tr[Max] ;
int n , p , s ; 
int Ans = 2e9 + 7 ; 
int main( ) {
//	freopen("1.in" , "r" , stdin ) ;
	scanf("%d%d%d" , &n , &p , &s ) ;
	for(int i = 1 ; i <= n ; i ++ ) scanf("%d%d" , &Tr[i].w , &Tr[i].v ) ;
	for(int l = 1 ; l <= s ; l ++ ) g[l] = 2e9 + 7 ;
	for(int i = 1 ; i <= n ; i ++ ) {
		for(int l = s ; l >= Tr[i].w ; l -- ) {
			if( f[l] < p ) {
				if(  f[l - Tr[i].w] + Tr[i].v > f[l] ) {
					f[l] = f[l - Tr[i].w] + Tr[i].v ; 
					g[l] = max( g[l - Tr[i].w] , Tr[i].w ) ; 
				} else if( f[l - Tr[i].w] + Tr[i].v == f[l] && max( g[l - Tr[i].w] , Tr[i].w ) < g[l] ) {
					f[l] = f[l - Tr[i].w] + Tr[i].v ; 
					g[l] = max( g[l - Tr[i].w] , Tr[i].w ) ; 
				}
			}
			if( f[l - Tr[i].w] + Tr[i].v >= p && max( g[l - Tr[i].w] , Tr[i].w ) < g[l] ) {
			//	cout << i << ' ' << l << ' ' << g[l - Tr[i].w] << ' ' << Tr[i].w << ' ' << "Yes\n" << endl ;
				f[l] = f[l - Tr[i].w] + Tr[i].v ; 
				g[l] = max( g[l - Tr[i].w] , Tr[i].w ) ; 
			}
		}
	} 
	for(int i = s ; i >= 0 ; i -- ) 
		if( f[i] >= p ) Ans = min( Ans , g[i] ) ;
	if( Ans == 2e9 + 7 ) printf("No Solution!\n") ;
	else printf("%d\n" , Ans ) ;
	return false ; 
} 

求助，哪里错了qwq

这种思路是不是会考虑少或多还是本身就有问题呢qwq