EOJ-2064 Bookshelf 2

http://acm.cs.ecnu.edu.cn/problem.php?problemid=2064

大致题意：给出一些物品的体积与体积上限，选出一些物品，使得物品总体积大于等于体积上限且差值最小，求出这个差值

n<=20 ,而 V <= 20*10^6 故不能DP，而n较小则用DFS+剪枝。(最终0 ms)

每种物品选或不选则复杂度2^n。

可行性剪枝：若当前总体积加上"之后所有物品的总体积"小于体积上限，则剪枝

最优化剪枝：若 "当前的总体积减去体积上限 "已经大于之前得出的解，则剪枝

 1 #include<map>
 2 #include<set>
 3 #include<list>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<queue>
 7 #include<stack>
 8 #include<cctype>
 9 #include<cstdio>
10 #include<string>
11 #include<vector>
12 #include<cstdlib>
13 #include<cstring>
14 #include<iostream>
15 #include<algorithm>
16 using namespace std;
17 int a[21],nextSum[21];            //nextSum[i]表示从i开始之后所有物品的体积总和(包括i)
18 int n,b;
19 int ans;
20 void dfs(int depth,int height){
21     if(height+nextSum[depth]<b) return ;//可行性剪枝    
22     if(height-b>=ans) return ;            //最优化剪枝
23     
24     if(depth==n+1){
25         if(height>=b)
26             ans=min(ans,height-b);        //得到最优解
27         return ;
28     }
29     dfs(depth+1,height);
30     dfs(depth+1,height+a[depth]);        //选与不选
31 }
32 int main(){
33     while(~scanf("%d%d",&n,&b)){
34         for(int i=1;i<=n;i++)
35             scanf("%d",a+i);
36         for(int i=1;i<=n;i++)
37             for(int j=i;j<=n;j++)
38                 nextSum[i]+=a[j];        //预处理nextSum数组
39         ans=0x3f3f3f3f;
40         dfs(1,0);
41         printf("%d
",ans);
42     }
43     return 0;
44 }

View Code

Ps： DP也能ac

 1 #include<map>
 2 #include<set>
 3 #include<list>
 4 #include<cmath>
 5 #include<ctime>
 6 #include<queue>
 7 #include<stack>
 8 #include<cctype>
 9 #include<cstdio>
10 #include<string>
11 #include<cstdlib>
12 #include<cstring>
13 #include<iostream>
14 #include<algorithm>
15 using namespace std;
16 int dp[1000005],h[25];
17 int main(){
18     int n,b;
19     while(~scanf("%d%d",&n,&b)){
20         int H=0;
21         for(int i=1;i<=n;i++){
22             scanf("%d",h+i);
23             H+=h[i];
24         }
25         memset(dp,0,sizeof(dp));
26         for(int i=1;i<=n;i++)
27             for(int j=H;j>=h[i];j--)
28                 dp[j]=max(dp[j],dp[j-h[i]]+h[i]);
29         for(int i=0;i<=H;i++)
30             if(dp[i]>=b){
31                 printf("%d
",dp[i]-b);
32                 break;
33             }
34     }
35     return 0;
36 }

View Code