#include <stdio.h>
#include <stdlib.h>
#define MAXN 20
int N, Cnt;
long W[MAXN][2];
long total, half;
long res;
int mark[MAXN], used[MAXN];
void DFS(long cur, int p)
{
int i;
if (res < cur)
{
res = cur;
for (i=0; i<N; i++)
mark[i] = used[i];
}
for (i=p; i<Cnt && res!=half && cur+W[i][0]<=half; i++)
if (used[i] < W[i][1])
{
used[i]++;
DFS(cur+W[i][0], i);
used[i]--;
}
}
int Comp(const void *p1, const void *p2)
{
long e1 = *((long *)p1);
long e2 = *((long *)p2);
if (e1 >= e2)
return 1;
else
return -1;
}
void Work()
{
int i;
qsort(W, Cnt, sizeof(long)*2, Comp);
res = 0;
for (i=0; i<Cnt; i++)
mark[i] = used[i] = 0;
if (W[Cnt-1][0] >= half)
{
res = W[Cnt-1][0];
mark[Cnt-1] = 1;
return;
}
DFS(0, 0);
}
int ReadData()
{
int i, j;
long val;
if (scanf("%d", &N) == EOF)
return 0;
total = 0;
Cnt = 0;
for (i=0; i<N; i++)
{
scanf("%ld", &val);
total += val;
for (j=0; j<Cnt; j++)
if (W[j][0] == val)
{
W[j][1]++;
break;
}
if (j == Cnt)
{
W[Cnt][0] = val;
W[Cnt][1] = 1;
Cnt++;
}
}
half = total/2;
return 1;
}
void Display()
{
int i, j;
printf("\nheap 1 = %ld:", res);
for (i=0; i<Cnt; i++)
for (j=0; j<mark[i]; j++)
printf(" %ld", W[i][0]);
printf("\nheap 2 = %ld:", total-res);
for (i=0; i<Cnt; i++)
for (j=0; j<W[i][1]-mark[i]; j++)
printf(" %ld", W[i][0]);
printf("\n\n");
}
int main()
{
int T = 1;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while (ReadData())
{
Work();
printf("Case #%d\n", T);
Display();
T++;
}
return 0;
}
正文
类背包问题2005-02-17 19:35:00
【评论】 【打印】 【字体:大 中 小】 本文链接:http://blog.pfan.cn/book/217.html
阅读(263) | 评论(0)
版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!
评论