背包问题（C++）深搜

问题描述：

假设有n件质量分配为w1，w2，...，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+...+wik=T。若能，则背包问题有解，否则无解。

(例如：有5件可选物品，质量分别为8千克、4千克、3千克、5千克、1千克。假设背包的最大转载质量是10千克。)

算法分析：

1. 本题01背包问题，每个物体有选和不选两种状态，结果只进行有误解的判断。
2. 若dfs到有解，则不必继续深搜了。

若果当前物品选了无解，可以尝试不选是否有解，为了提高效率，方便剪枝，可以再加一个变量，当前选中物品的重量。

算法代码：

#include

using namespace std;

int n,T,ans=0;

int w[100];

bool dfs(int k, int t){

    if(t==0 )

          return true;

    if(k>n )

         return false;

     if(t<0)

            return false;

      if(dfs(k+1,t-w[k]))

           return true;

      else

          return dfs(k+1,t);

}

int main(){

    cin>>n>>T;

    for(int i=1;i<=n;i++)

          cin>>w[i];

    if(dfs(1,T))

         cout <<1;

    else cout<<0;

}