一本通1267 01背包问题（深度搜索 动态规划）

1267 01背包问题
【题目描述】
一个旅行者有一个最多能装 MM 公斤的背包，现在有 nn 件物品，它们的重量分别是W1，W2，…,WnW1，W2，…,Wn,它们的价值分别为C1,C2,…,CnC1,C2,…,Cn，求旅行者能获得最大总价值。

【输入】
第一行：两个整数，MM(背包容量，M≤200M≤200)和NN(物品数量，N≤30N≤30)；
第2…N+12…N+1行：每行二个整数Wi，CiWi，Ci，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。
【输入样例】
10 4
2 1
3 3
4 5
7 9

【输出样例】
12

个人思路：
本道题是一道动态规划问题，使用深度优先搜索。
此问题是探索每一个物体是否要放入背包，放与不放有两种选择，每一层次是一个物品。一共2^n中放法。叶子结点是方案。
剪枝：
1、如果这个物品的重量大于背包剩余重量的话，放不了，剪掉。
2、如果不放这个物品的话，剩余没有在背包中的物品的总价值没有这个物品的价值大的话，那就没有必要探索这条路了（反正剩下的所有物品都放进去的话也不会有放这个物品的价值大），剪掉。

如图:

代码：

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;

int m,n;
int v[31][2];//物体的重量和价值 
bool b[31];//标记物体的数组 
int value=0;//背包现在装载的价值 
int value_max=0;//背包装的最大价值 
int value_sheng=0;//剩余没有装的物品的总价值 
int w_sheng;//背包剩余重量 


int dfs(int i)//第几个物体
{
 if(i>n)//叶子结点才是结果
 {
  if(value_max<value)
   value_max=value; 
  return 0;
 }
 if(b[i]==0&&v[i][0]<=w_sheng)//如果这个物品没被装，且它的重量背包可以承受的话 
 {
  b[i]=1;//标记装上了
  value+=v[i][1];
  value_sheng-=v[i][1];
  w_sheng-=v[i][0]; 
  dfs(i+1); 
  if(!(value_sheng<=v[i][1]))//如果剩余的物品的价值还不如这个物品的价值的话，就不用再遍历没有这个物品的时候了 
  {                      //剪枝 
   b[i]=0;//回溯 
   value-=v[i][1];
   value_sheng+=v[i][1];
   w_sheng+=v[i][0];
   dfs(i+1);//不装这个物品的话 
  }
 }
 else//不能装这个物品 
 {
  dfs(i+1);
 }
 } 


int main()
{
 cin>>m>>n;
 w_sheng=m; 
 memset(b,0,sizeof(b));//初始化物体都没有放 放了以后就置1 
 for(int i=1;i<=n;i++)
 {
  cin>>v[i][0]>>v[i][1];
  value_sheng=value_sheng+v[i][1];
 }
 dfs(1);
 
 cout<<value_max;
 return 0;
}