动态规划:背包问题

istvh

问题描述：有不同大小于价值的物品，现只有一个容积为M的背包来装物品。请找出一种最优组合是价值最大化。
递归实现：
               
               
                int knap(int cap)
{
  int i, space, max, t;
  for (i = 0, max = 0; i  N; i++)
    if ((space = cap-items.size) >= 0)
      if ((t = knap(space) + items.val) > max)
    max = t;
  return max;     
}
动态规划实现：
int knap(int M)
{
  int i, space, max, maxi, t;
  if (maxKnown[M] != unknown) return maxKnown[M];
  for (i = 0, max = 0; i  N; i++)
    if ((space = M-items.size) >= 0)
      if ((t = knap(space) + items.val) > max)
    { max = t; maxi = i; }
  maxKnown[M] = max; itemKnown[M] = items[maxi];
  return max;     
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/99982/showart_2091185.html