动态规则算法之0－1背包问题

/*
 * Filename: knapsack.c
 *
 * Function: 0-1背包问题的动态规划算法
 *
 * Note：需要注意的是下标是从0开始的，而背包容易应该至少为1，
 *       而我们用的其下标作为其容量，所以在比较过程中应该加1
 *       它不像线路布线问题一样是一个二值问题，只涉及选或者不选，
 *       所以它的边界应该特殊处理。
 *
 * Version: 1.0
 * Author:  WUSW
 * Date:    2009.4.28
 */

#include

#define NUM 5
#define CAP 10

int max(int a, int b)
{
  return a>b?a:b;
}

/*
 * c: 背包容量
 * w: 物品重量数组
 * v: 物品价值数组
 * worth: 背包中的物品的价值
 */
void knapsack(int c, int w[NUM], int v[NUM], int worth[][CAP])
{
  int i = NUM - 1;        /* 当前要处理的物品号 */
  int j = 0;            /* 背包容量 */

  /* 处理边界 */
  for (j=0; j    {
      if (j+1 < w[i])    /* 背包容量至少为1，但是下标从0开始，所以在比较时加1 */
    {
      worth[i][j] = 0;
    }
      else
    {
      worth[i][j] = v[i];
    }
    }

  for (--i; i>=0; i--)
    {
      for (j=0; j    {
      if (j+1 < w[i])
        {
          worth[i][j] = worth[i+1][j];
        }
      else
        {
          worth[i][j] = max(worth[i+1][j], worth[i+1][j-w[i]]+v[i]);
        }
    }

    }
}

/* 回溯得到被选择的物品 */
void traceback(int worth[][CAP], int w[NUM], int in[NUM])
{
  int i = 0;
  int j = CAP-1;
 
  for (i=0; i    {
      if (worth[i+1][j] != worth[i+1][j-w[i]])
    {
      in[i] = 1;
      j -= w[i];
    }
    }
  if (j > worth[i][j])
    {
      in[i] = 1;
    }
 
}


int main(int argc, char * argv[])
{

  int w[NUM] = {2, 2, 6, 5, 4};
  int v[NUM] = {6, 3, 5, 4, 6};
  int in[NUM] = {0} ;
  int worth[NUM][CAP] = {{0}};
 
  knapsack(CAP, w, v, worth);
  traceback(worth, w, in);

  int i = 0;

  for (i=0; i    {
      printf("%d ", in[i]);
    }
  printf("\n");
 
 

  return 0;
}