P2918 [USACO08NOV]买干草Buying Hay

链接：Miku

这就是一个完全背包的板子题

我们把重量当作重量，开销当作价值，那么这个题就是个求价值最小的完全背包

然而题目上说了是不少于，也就是说最优解不一定恰好就是买h磅的时候，怎么办呢？

只要多余h就行了的话，我们就在h+x的范围内找一个最小值不就可以了？

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 int dp[55001];
 7 int h;
 8 int n;
 9 int w[101];
10 int v[101];
11 int main(){
12     scanf("%d%d",&n,&h);
13     for(int i=1;i<=n;++i){
14         scanf("%d%d",&w[i],&v[i]);
15     }
16     memset(dp,0x7f7f,sizeof(dp));
17     h+=1000;
18     dp[0]=0;
19     for(int i=1;i<=n;++i){
20         for(int j=w[i];j<=h;++j){
21                 dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
22         }
23     }
24     int ans=0x7f7f7f;
25     for(int i=h-1000;i<=h;++i){
26     //    cout<<i;
27     //    cout<<dp[i]<<endl;
28         ans=min(ans,dp[i]);
29     }
30     cout<<ans;
31     return 0;
32 }

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论