#include<iostream>using namespace std; //显然定义为全局变量不好 const int item=3;//物品数量const int max_wgt=10;//背包最大容量int c[item+1][max_wgt+1];//从1…i…item物品中,背包剩余空间为0<=j<=max_wgt的最大价值  int w[item+1]={0,3,4,5};//物品质量 int vl[item+1]={0,4,5,6}; //物品价值 int knapbag(){     for (int i=0;i<=item;i++)//初始化   {      for (int j=0;j<=max_wgt;j++)      {         c[i][j]=0;      }   }   //c(i,j)=max{c(i-1,j), c(i-1,j-w[i])+vl(i)}   for (int i=1;i<=item;i++)   {      for (int j=1;j<=max_wgt;j++)      {         if (w[i]<=j)         {             if (vl[i]+c[i-1][j-w[i]]>c[i-1][j])             {                  c[i][j]=vl[i]+c[i-1][j-w[i]];//选择第i物品             }             else                  c[i][j]=c[i-1][j];//不选择第i个物品         }         else             c[i][j]=c[i-1][j];//剩余容量不够     }//endfor   }//endfor   return c[item][max_wgt];//返回最大值} int main(){  cout<<knapbag()<<endl;  return 0;} void trackback()//算出是由哪几个物品组成{    int temp_wei=max_wgt;    int x[item+1]={0,0,0,0};    for (int i=item;i>0;i--)    {      if (c[i][temp_wei]==c[i-1][temp_wei])//最后一个肯定是最大价值的      {         x[i]=0;      }      else      {        x[i]=1;        temp_wei-=w[i];      }    }    for (int i=0;i<=item;i++)    {      if (x[i])      {        std::cout<<i<<",";      }    }    std::cout<<std::endl;} 注：已编译通过，但还需优化。如果有更佳算法，请email交流：hym4682@126.com 如果你是c++高手，请加群75279426。

评论