ACM记录之01背包问题动态规划求解思路

01背包问题（knapsack problem)

==============================================================

问题描述：

从N件物品中选取若干件物品放入空间大小为M的背包中，每件物品都其体积和价值
，体积分别为w[1],w[2],w[3] … w[n] ,价值分别为p[1]，p[2],p[3], … p[n] 。

求解将哪些物品装入背包可使价值总和最大。

==============================================================

动态规划求解思路：

阶段： 前n件物品中，选若干件放入背包

状态： 前n件物品中，选取若干件物品放入所剩空间为Mo的背包中所能获得的最大价值

决策： 第n件物品放或者不放入

动态转移方程：

        f[i,j]=max{ f[i-1,j-w[i]+p[i]  (j>=w[i]) ,  f[i-1,j] }

其中：f[i,j]表示在前i件物品中选择若干件放入所剩空间为j的背包中所能获取的最大价值

==============================================================

代码：

#include<conio.h>

int main()
 {
  int m,n,i,j;
  int w[20],p[20];
  int f[20][100];  //f[i][j]表示在前i件物品中选择若干件放入所剩空间为j的背包中所能获取的最大价值

  printf("input n m:");  //物品的数量 背包空间
  scanf("%d %d",&n,&m);
  printf("input w[i] p[i]:\n\a"); //第i个物品的体积和价值

  for(i=1;i<=n;i++)
    scanf("%d %d",&w[i],&p[i]);

  for(j=0;j<=m;j++)
    f[0][j]=0;
  
  for(i=1;i<=n;i++)
   {
    for (j=0;j<=m;j++)
     {
       if (j>=w[i])
        {
          if(f[i-1][j-w[i]] + p[i] > f[i-1][j])
           f[i][j]=f[i-1][j-w[i]] + p[i];
          else
           f[i][j]=f[i-1][j];
         }
       else
         f[i][j]=f[i-1][j];
     }
   }

  printf("max=%d",f[n][m]);
  getch();
  return 0;
 }

Views: 94