A Good Helper
| Source : HCPC 2004 |
| Time limit : 1 sec |
| Memory limit : 32 M |
Submitted : 476, Accepted : 205
Abraham and Calford are Moving their things from dormitory A11 to A9,and they have their own carry limit,they can't carry things which is beyond their limit and they will not carry one bag together. They want things to be carried in one time,when they can't deal with so many things, they will hire a good helper to help them, who can only carry one bag of things, regardless of the weight of it. Your task is to tell whether they can carry their bags in one time,or not.
Input
There are multiple test cases.
First line of each test case contains two nonnegative numbers, A and C, (0 < A,C <=1000) representing the limit of Abraham and Calford,then the second line contains an integer N ( 0 < N <= 200 ) ,representing the number of bags,followed by N positive integers,each of them is not more than 100.
Output
For each test case
Output "Yes" if they can carry the bags without the help of the helper in one time.
Output "Need a helper" if they can only carry the bags with the help of the helper in one time.
Output "No" if they can't carry the bags in one time.
Sample Input
7 7
3 5 5 5
7 7
3 5 2 5
7 7
3 7 8 7
7 7
3 7 8 9
Sample Output
Need a helper
Yes
Need a helper
No
額，這個題有兩個包，還有一個good helper，當時不知道怎么寫，覺著是dp，然后想出了個二維的方程，復雜度奇高
然后找了下題解才發現可以這樣做
只對第一個人dp，如果讓第一個人盡量裝，然后看剩下的第二個人能不能全部帶走，如果可以則Yes
不行則看，如果去除重量最大的一個兩個人能不能拿走，可以則Need a helper 否則No
這個helper可以拿任意重的東西，所以如果可能則可以選擇把最重的物品給他
我們可以在預處理的時候把最終的放到最后面
f[i][j]表示前i件物品，用j的重量時候能拿走的最大重量
然后這樣就是個簡單的一維背包了，那么f[n-1][a]則是出去最重一個物品后能取得的最大值
根據背包九講，我們可以優化空間到一維，但在枚舉費用時候要倒序
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 int f[1300],a,c;
5 int n,v[240];
6 int big,tmp,xi;
7 int tot;
8 void init()
9 {
10 int i,temp;
11 scanf("%d",&n);
12 big=0;
13 tot=0;
14 for(i=1;i<=n;i++)
15 {
16 scanf("%d",&v[i]);
17 tot+=v[i];
18 if (v[i]>big)
19 {
20 big=v[i];
21 xi=i;
22 }
23 }
24 temp=v[xi];v[xi]=v[n];v[n]=temp;
25 }
26 int max(int a,int b)
27 {
28 if (a>b) return a; else return b;
29 }
30 void work()
31 {
32 int i,j;
33 memset(f,0,sizeof(f));
34 for (i=1;i<=n ;i++ )
35 {
36 for (j=a;j>=v[i] ;j-- )
37 {
38 tmp=f[a];
39 f[j]=max(f[j-v[i]]+v[i],f[j]);
40 }
41 }
42 if (f[a]+c>=tot) printf("Yes\n");
43 else if (tmp+c>=tot-big) printf("Need a helper\n");
44 else printf("No\n");
45 }
46 int main()
47 {
48 while (scanf("%d%d",&a,&c)!=EOF)
49 {
50 init();
51 work();
52 }
53 return 0;
54 }
55