【前言】

今天是力扣打卡第13天！

加油啦！!

原题：背包问题（DFS）

题目描述：

有n件物品，每件物品的重量为w[i], 价值为c[i]。现在需要选出若干件物品放入一个容量为v的背包中，使得在选入背包的物品重量和不超过容量v的前提下，让背包中物品的价格之和最大，求最大价值。

示例：

  

   

    

     

    
    

     

      输入：物品重量：3 5 1 2 2  物品价值：4 5 2 1 3
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      输出：10
     
    
  
 

题解：

在这个问题中，需要从n件物品中选择若干件物品放入背包，使它们的价值之和最大。这样的话，对每件物品都有选和不选两种选择，而这就是所谓的“岔道口”。而当完成对于n件物品的选择之后就到达了“死胡同”，不过本题需要额外再多考虑一种情况，题目要求选择的物品总和不能超过v，因此一旦选择的物品重量总和超过v,也就会到达“死胡同”，所以这道题目需要多考虑一下，铁汁们要小心哦，具体的看代码实现。

代码实现：

  

   

    

     

    
    

     

      ​
     
    
   

    

     

    
    

     

      //题目：有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;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      ​
     
    
  
 

结语

今天是力扣打卡第13天！

加油哦铁汁们，不负韶华！！

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121273273