hdu 1059 dividing

背包问题,考虑是先计算出总量的一半,然后判断能否把这个背包装满。

觉得这题自己有点乱搞,虽然用下面的算法把它AC了,可能是数据太弱了,觉得这个算法还是有点问题。

PE了一次,原来是每组数据后都要一个n.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <stdlib.h>
#include <string.h>
int w[7] = {0};
int (int T,int p)
{
if ( p < 1) return 0;
if (!T) return 1;

while (w[p] == 0 || p > T) p--;
w[p]--;
//做二分选择放入背包和不放入背包
return ( knap(T-p,p) || knap(T,p-1));
}
int main()
{
freopen("Sample Input.txt","r",stdin);
int cse;
int i,Flag;
int HalfSpace;
cse = 1;
while ( scanf("%d%d%d%d%d%d",&w[1],&w[2],&w[3],&w[4],&w[5],&w[6]),w[1]||w[2]||w[3]||w[4]||w[5]||w[6])
{
HalfSpace = 0;
for ( i = 1; i <= 6; i++)
HalfSpace += w[i]*i;
if ( HalfSpace%2 ) Flag = 0;
else
{
HalfSpace/=2;
Flag = knap(HalfSpace,6);
}
printf("Collection #%d:n",cse++);
if ( Flag )
printf("Can be divided.nn");
else
printf("Can't be divided.nn");
}
return 0;
}