1606: [Usaco2008 Dec]Hay For Sale 購買干草

Time Limit:?5 Sec??Memory Limit:?64 MB
Submit:?1335??Solved:?989
[Submit][Status][Discuss]

Description

約翰遭受了重大的損失：蟑螂吃掉了他所有的干草，留下一群饑餓的牛．他乘著容量為C(1≤C≤50000)個單位的馬車，去頓因家買一些干草．??頓因有H(1≤H≤5000)包干草，每一包都有它的體積Vi(l≤Vi≤C).約翰只能整包購買， 他最多可以運回多少體積的干草呢？

Input

第1行輸入C和H，之后H行一行輸入一個Vi．

Output

最多的可買干草體積．

Sample Input

7 3 //總體積為7,用3個物品來背包
2
6
5


The wagon holds 7 volumetric units; three bales are offered for sale with
volumes of 2, 6, and 5 units, respectively.

Sample Output

7 //最大可以背出來的體積

HINT

?

Buying the two smaller bales fills the wagon.

?

Source

Silver

?

Analysis

針對性優化的背包類DPqwq

一開始口胡了一個貪心（降序排序后枚舉最大值，然后開始遍歷arr往addup里塞草包，如果當前值不合法就跳過找下一個值），居然過了！！！

好吧，還是被CZL一波Hack... 果然是數據太水

后來被LLQ一波對拍打出了問題所在：

如果正解有不連續的元素，貪心會被輕松卡掉（比如5 4 3 2，以上策略優先選5+4然后跳過5）

?

Code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #define maxn 100000
 5 using namespace std;
 6 
 7 int arr[maxn],n,T,ans;
 8 
 9 bool cmp(const int a,const int b){
10     return a>b;
11 }
12 
13 int main(){
14     scanf("%d%d",&T,&n);
15     
16     for(int i = 1;i <= n;i++){
17         scanf("%d",&arr[i]);
18     }
19     
20     sort(arr+1,arr+1+n,cmp);
21     
22     for(int i = 1;i <= n;i++){
23         int addup = 0;
24         for(int j = i;j <= n;j++){
25             if(addup+arr[j] <= T){
26                 addup += arr[j];
27             }
28         }
29         ans = max(ans,addup);
30     }
31     
32     printf("%d",ans);
33     
34     return 0;
35 }

神奇的貪心版本

 1 #include<cstdio>
 2 #include<iostream>
 3 #define maxn 1000000
 4 using namespace std;
 5 
 6 int DP[maxn],n,m,cnt;
 7 
 8 int main(){
 9     
10     scanf("%d%d",&n,&m);
11     
12     for(int i = 1;i <= m;i++){
13         scanf("%d",&cnt);
14         DP[cnt] = 1;
15         for(int j = n;j >= cnt;j--){
16             DP[j] = DP[j]|DP[j-cnt];
17         }
18     }
19     
20     int ans = n;
21     while(!DP[ans]) ans--;
22     
23     printf("%d",ans);
24     
25     return 0;
26 }

針對性優化背包版本

轉載于:https://www.cnblogs.com/Chorolop/p/7460523.html

總結

以上是生活随笔為你收集整理的[BZOJ] 1606: [Usaco2008 Dec]Hay For Sale 购买干草的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。