正文

类背包问题2005-02-17 19:35:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/book/217.html

分享到:

#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;
}

阅读(263) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册