#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。

评论