编辑代码

#include<iostream>
#include<math.h>

using namespace std;

//用于记录是否存放当前地物体
int inOut[4];
//保存最多的价值
int value;
//定义背包的总共的重量的
int bagVolume = 9;


bool bagConstraint(int m, int weight[]) {
 //一直遍历m层之前的所有物体,求出其对应的重量
 int allweight = 0;
 for (int i = 0; i <= m; ++i)
 {
  //计算出总共的重量的
  allweight += inOut[i] * weight[i];
 }

 //比较当前的物体总重量和背包的总重量关系
 return allweight <= bagVolume;
}

/*
 描述:深度优先搜索的函数,递归函数
 参数:m:是要装入背包的物品的数量
   weight:是背包中各个物品的重量
   value:是背包中各个物品的价值
 返回:最终返回的是最大的价值
 问题:
*/
void bagProblem(int m, int weight[], int valueAll[]) {

 //首先确定终止条件,那就比较最大值
 if (m == 4)
 {
  int sum = 0;
  for (int i = 0; i < m; ++i)
  {
   sum += valueAll[i] * inOut[i];
  }

  //比较最大值
  if (sum > value)
  {
   value = sum;
  }
 }
 else {
  //没有到达终止条件,继续向下进行递归
  for (int i = 0; i < 2; ++i)
  {
   inOut[m] = i;
   //判定是否满足对应约束条件
   if (bagConstraint(m, weight))
   {
    //满足约束条件,继续向下进行递归的
    bagProblem(m + 1, weight, valueAll);
   }
  }

 }

}

int main(int argc, char const* argv[])
{
 cout << "输入的样例:物品数量:4" << endl;
 cout << "背包容量:9" << endl;
 cout << "重量分别是:2 3 4 5" << endl;
 cout << "价值分别是:3 4 5 6 " << endl;
 int num = 4;
 int weight[4] = { 2,3,4,5 };
 int valueAll[4] = { 3,4,5,6 };
 bagProblem(0, weight, valueAll);
 cout << "最终的结果是:" << value << endl;
 cout << endl;
 return 0;

}