​
//题目：有n件物品，每件物品的重量为w[i],价值为c[i](由于每件都不同，所以采用i表示变化的意思)。现在需要选出若干件物品放入一个
//容量为V的背包中，使得在选入背包的物品重量和不超过V的前提下，让背包中物品的价值之
//和最大，求最大价值(1 <= n <= 20)
#include<stdio.h>
int maxValue = 0;//最大价值
//下面四组数据可以自己设定，由于想简化题目所以在这里直接以全局变量的形式给出
int n = 5;//物品数目
int v = 8;//背包容量
int w[] = { 3,5,1,2,2 };//w[i]为每件物品重量
int c[] = { 4,5,2,1,3 };//c[i]为每件物品价值
//index为当前处理物品的下标（物品下标范围是0~n - 1）
//sumW和sumC分别为当前总重量和当前总价值
void DFS(int index, int sumW, int sumC)
{
  //已经完成了对n件物品的选择（递归边界--死胡同）
  if (index == n)
  {
    return;
  }
    //岔道口
  DFS(index + 1, sumW, sumC);//不选第index件物品
  //只有加入第index件物品后未超出容量v,才能继续执行（注意这个限制条件）
  if (sumW + w[index] <= v)
  {
    //注意哦，如果加入第index件物品后总价值大于最大价值maxValue时记得要更新最大价值
    if (sumC + c[index] > maxValue)
    {
      maxValue = sumC + c[index];//更新最大价值maxValue
    }
    DFS(index + 1, sumW + w[index], sumC + c[index]);//选择第index件物品
  }
}
int main()
{
  DFS(0, 0, 0);//初始时为第0件物品、当前总重量和总价值均为0
  printf("满足条件的最大价值为：%d\n", maxValue);
  return 0;
}