背包问题~~！C++

5 10 //5代表5件物品 10代表 取这5件物品种 哪几样 可以加起来为10
1 2 3 4 5

//第1件物品重量1
//第2件物品重量2
//第3件物品重量3
//第4件物品重量4
//第5件物品重量5

现在我们想，我们有一个布袋，初始状态里面是空的，意味着哪几方面信息？
第一， 重量为0
第二， 物品个数为0
第三， 总重量不等于10

以上状态我们用0来表示

接下来我们分析我们对第一个物品可以做的事，就是把他放进布袋，或不放进布袋
那们结合前面的0状态，再加上第一个物品的两个状态就可以看到以下情况：

0 0 1 0代表不取 1代表取

如果这看明白了，在对一个物品处理之后，就是处理第二个物品

是不是：

0

0 1
0 1 0 1
同样第三个，第四个也是这原理

0

0 1
0 1 0 1
0 1 0 1 0 1 0 1
…

如果以上能理解了，就应当有递归的感觉了
题目要求：找到一组解即可。说明会有很多情况其实是可以满足要求的：
比如上面的案例： 1234为10 145为10 235为10
接下来用代码写函数

510//5代表5件物品 10代表 取这5件物品种 哪几样 可以加起来为1012345//第1件物品重量1//第2件物品重量2//第3件物品重量3//第4件物品重量4//第5件物品重量5现在我们想，我们有一个布袋，初始状态里面是空的，意味着哪几方面信息？ 第一， 重量为0第二， 物品个数为0第三， 总重量不等于10以上状态我们用0来表示 接下来我们分析我们对第一个物品可以做的事，就是把他放进布袋，或不放进布袋 那们结合前面的0状态，再加上第一个物品的两个状态就可以看到以下情况：0010代表不取1代表取 如果这看明白了，在对一个物品处理之后，就是处理第二个物品 是不是：0010101同样第三个，第四个也是这原理001010101010101.....如果以上能理解了，就应当有递归的感觉了 题目要求：找到一组解即可。说明会有很多情况其实是可以满足要求的： 比如上面的案例：1234为10145为10235为10接下来用代码写函数#include<iostream>usingnamespacestd;typedefstruct{intindex;intvalue;}Data;inta[10000],s,n;Data data[10000];intsize;boolcheck(intSumweigth,intcnt){if(cnt==-1)returnSumweigth==s;//如没有可选,返回布袋与要求的是否一致elseif(check(Sumweigth+a[cnt],cnt-1)){//当前位置放入布袋继续分析data[size].index=cnt;data[size].value=a[cnt];size++;returntrue;}elseif(check(Sumweigth,cnt-1)){//当前位置没进包里，继续分析returntrue;}returnfalse;}voidprint(){for(inti=0;i<size;i++)cout<<"number:"<<data[i].index+1<<" weight:"<<data[i].value<<endl;//index+1 因为下标是从0开始的}voidsolve(){cin>>n>>s;for(inti=0;i<n;i++)cin>>a[i];if(check(0,n-1))print();elsecout<<"not found"<<endl;}intmain(){solve();return0;}