bag.c

在0 / 1背包问题中

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//goods是一个或多个物品的重量和价值

typedef struct goods
{
  int weight;
  int value;
} goods;

//用来定义一个queryList数组

//数组中的每个元素定义一趟需要记录的数据

typedef struct queryList
{
  goods *subResult; //一趟需要记录的数据

  int end; //指示该趟数据的最后一个元素

} queryList;

queryList* dknap(goods *Goods, int count, int capacity)
{
  int i, j, next, pre, index, k;
  queryList *ql;
  goods cur;
  ql = (queryList *)malloc(sizeof(queryList)*count);
  ql[0].subResult = (goods*)malloc(sizeof(goods));
  ql[0].end = 0;
  ql[0].subResult->weight = 0;
  ql[0].subResult->value = 0;

  for(i=1;i<count;i++)
  {
    pre = 0;
    index = 0;
    ql[i].subResult = (goods*)malloc(sizeof(goods)*(ql[i-1].end+1)*2);
    cur.weight = ql[i-1].subResult[0].weight + Goods[i-1].weight;
    cur.value = ql[i-1].subResult[0].value + Goods[i-1].value;
    next = 1;


    //合并生成新的一趟需要记录的数据, 类似于merge sort
    while (pre<ql[i-1].end+1)
    {
      if (cur.weight>ql[i-1].subResult[pre].weight)
        if (cur.value <= ql[i-1].subResult[pre].value) //抛弃新生成元素
        {
          cur.weight = ql[i-1].subResult[next].weight + Goods[i-1].weight;
          cur.value = ql[i-1].subResult[next].value + Goods[i-1].value;
          next++;
        }
        else //插入旧元素
        {
          ql[i].subResult[index].weight = ql[i-1].subResult[pre].weight;
          ql[i].subResult[index].value = ql[i-1].subResult[pre].value;
          pre++;
          index++;
        }
      else
        if (cur.weight<ql[i-1].subResult[pre].weight)
          if (cur.value >= ql[i-1].subResult[pre].value) //抛弃旧元素
            pre++;
          else  //插入新生成元素
          {
            ql[i].subResult[index].weight = cur.weight;
            ql[i].subResult[index].value = cur.value;
            index++;
            cur.weight = ql[i-1].subResult[next].weight + Goods[i-1].weight;
            cur.value = ql[i-1].subResult[next].value + Goods[i-1].value;
            next++;
          }
        else
          if (cur.value >= ql[i-1].subResult[pre].value) //抛弃旧元素
            pre++;
          else  //抛弃新生成元素
          {
            cur.weight = ql[i-1].subResult[next].weight + Goods[i-1].weight;
            cur.value = ql[i-1].subResult[next].value + Goods[i-1].value;
            next++;
          }
    }
    //插入剩余的新生成元素
    for(j=next-1;j<ql[i-1].end+1;j++)
    {
      if (ql[i-1].subResult[j].weight + Goods[i-1].weight > capacity)
        break;
      ql[i].subResult[index].weight = ql[i-1].subResult[j].weight + Goods[i-1].weight;
      ql[i].subResult[index].value = ql[i-1].subResult[j].value + Goods[i-1].value;
      index++;
    }
   
    ql[i].end=index-1;
    printf("i=%d\n", i);
    for(j=0;j<ql[i].end+1;j++)
      printf("(%d, %d)\n", ql[i].subResult[j].value, ql[i].subResult[j].weight);
  }

  finalResult(ql, Goods, count, capacity);
  for(i=0;i<count;i++)
    free(ql[i].subResult);
  free(ql);
  return ql;
  
}


//输出最终的取舍情况
int finalResult(queryList* ql, goods* Goods, int count, int capacity)
{
  int i, j, k;
  for(i=count-1;i>=0;i--)
  {
    k=ql[i].end;
    while (k>=0)
    {
      if (ql[i].subResult[k].weight>capacity)
        k--;
      else break;
    }
    j=k;
    while (j>=0)
    {
      if (ql[i].subResult[j].weight+Goods[i].weight>capacity)
        j--;
      else break;
    }
    
    if (k>=0 && j<0)
      printf("a[%d]=%d\n", i, 0);
    else if (k<0)
    {
      printf("unsatifitable\n");
      return -1;
    }
    else 
    {
      if (ql[i].subResult[k].value>=ql[i].subResult[j].value+Goods[i].value)
        printf("a[%d]=%d\n", i, 0);
      else
      {
        printf("a[%d]=%d\n", i, 1);
        capacity = capacity - Goods[i].weight;
      }
    }
  }
}

int main()
{
  goods Goods[] = {{2, 1}, {3, 2}, {4, 5}};
  dknap(Goods, sizeof(Goods)/sizeof(Goods[0]), 6);
  //goods Goods[] = {{100, 100}, {50, 50}, {20, 20}, {10, 10}, {7, 7}, {3, 3}};
  //dknap(Goods, sizeof(Goods)/sizeof(Goods[0]), 165);

  
}