题目 题意：求出满足在背包容量内，背包价值大于k的所有情况中，找到最小价值是最大的那一种情况。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <map> #include <set> #include <queue> #include <vector> #define mem(a) memset(a, 0, sizeof(a)) using namespace std; typedef pair<int, int> Pii; typedef long long LL; const int MAXN = 1005; const int inf = 0x3f3f3f3f; const int Mod = 100000000; inline int read() { int f=1, x=0; char ch = getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return f*x; } struct node{ int w, v; }a[MAXN]; bool cmp(node a, node b) { return a.v>b.v; } int n, m, k; int dp[MAXN]; bool judge(int mid) { mem(dp); for(int i=1;i<=n;++i) { if(a[i].v<mid)continue;//如果排过序，就break; for(int j=m;j>=a[i].w;--j) dp[j]=max(dp[j], dp[j-a[i].w]+a[i].v); } if(dp[m]>=k)return true; return false; } int main() { while(~scanf("%d %d %d", &n, &m, &k)) { for(int i=1;i<=n;++i) scanf("%d %d", &a[i].w, &a[i].v); int l=0, r=1000005; int ans=-1; //sort(a+1, a+1+n, cmp); while(l<=r) { int mid= (l + r)>>1; if(judge(mid)) { ans=mid; l=mid+1; } else r=mid-1; } printf("%d\n", ans); /* while(l<=r) { int mid= (l + r)>>1; if(judge(mid)) l=mid+1; else r=mid-1; } printf("%d\n", r); */ } return 0; }