Chinaunix首页 | 论坛 | 博客
  • 博客访问: 216158
  • 博文数量: 59
  • 博客积分: 4010
  • 博客等级: 上校
  • 技术积分: 900
  • 用 户 组: 普通用户
  • 注册时间: 2009-03-30 20:21
文章分类

全部博文(59)

文章存档

2011年(1)

2009年(58)

我的朋友

分类: C/C++

2009-05-18 20:03:02

/*
 * 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;
}
阅读(1281) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~