洛谷P 2370 yyy 2015 c 01のU盤

ジャンプをクリックして問題を理解
问题解:この问题を分析してみると、価値は最も重要ではありません(pさえあればいいので)、重要なのは、最小のインタフェースです.
だから貪欲な策略を応用して、私達は優先的にインタフェース(大きさ)の小さいを詰めて、それから毎回詰め終わって判断して、現在の価値が超えているかどうかを判断します
pを超えたら、これが最小の最大インタフェースで、すべてのものが入っていて、まだpに着いていないと、解がありません.
方法:欲張り+01リュック

 1 #include
 2 #include
 3 #include
 4 #include
 5 
 6 using namespace std;
 7 
 8 int dp[1005],n,p,s;
 9 struct node
10 {
11     int w,c;
12 };
13 node data[1005];
14 
15 inline bool cmp(node x,node y)
16 {
17     return x.w<y.w;
18 }
19 
20 int main()
21 {
22     scanf("%d%d%d",&n,&p,&s);
23     for(int i=1;i<=n;i++)
24         scanf("%d%d",&data[i].w,&data[i].c);
25     sort(data+1,data+n+1,cmp);
26     for(int i=1;i<=n;i++)
27         for(int v=s;v>=data[i].w;v--)
28         {
29             dp[v]=max(dp[v],dp[v-data[i].w]+data[i].c);
30             if(dp[v]>=p)
31             {
32                 printf("%d",data[i].w);
33                 return 0;
34             }
35         }
36     printf("No Solution!");
37     return 0;
38 }

 
転載先:https://www.cnblogs.com/Hoyoak/p/11379344.html