首页 > 代码库 > POJ 3628 Bookshelf 2

POJ 3628 Bookshelf 2

2024-07-17 07:35:53   213人阅读

POJ 3628 Bookshelf 2：http://poj.org/problem?id=3628

题意：有个书架，高度为B，现在FJ有N个奶牛，每个奶牛有个高度hi，现在将奶牛堆起来，使得堆起来的高度大于等于B，现在要求最小高度差。

思路一： 01背包：把奶牛的高度总和减去B，就是这个背包的容量，填充它，求出的最大值与背包的容量做差，结果就是他了。

CODE:

 1 #include<stdio.h> 2 #include<string.h> 3 int w[100],f[20000000]; 4 int max(int a,int b) 5 { 6     return a>b?a:b; 7 } 8 int main() 9 {10     int n,b,i,j;11     int sum=0;12     while(scanf("%d%d",&n,&b)!=EOF)13     {14         for(i=0;i<=n;i++)15             f[i]=0;16         sum=0;17         for(i=0; i<n; i++)18         {19             scanf("%d",&w[i]);20             sum+=w[i];21         }22         int k=sum-b;23         for(i=0; i<n; i++)24         {25             for(j=k; j>=w[i]; j--)26             {27                 f[j]=max(f[j],f[j-w[i]]+w[i]);28             }29         }30         printf("%d\n",k-f[k]);31     }32     return 0;33 }

思路二：DFS：（转）

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 #define maxn 25 7 int n, m; 8 int f[maxn], s[maxn]; 9 int ans;10 void dfs(int cow, int sum)11 {12     if (ans == 0)13         return;14     if (s[cow] + sum < m)15         return;16     if (sum >= m)17     {18         ans = min(ans, sum - m);19         return;20     }21     if (cow == n)22         return;23     dfs(cow + 1, sum);24     dfs(cow + 1, sum + f[cow]);25 }26 int main()27 {28     scanf("%d%d", &n, &m);29     for (int i = 0; i < n; i++)30         scanf("%d", &f[i]);31     s[n] = 0;32     for (int i = n - 1; i >= 0; i--)33         s[i] = s[i + 1] + f[i];34     ans = 0x3f3f3f3f;35     dfs(0,0);36     printf("%d\n", ans);37     return 0;38 }

 


联系
我们