文章
3
粉丝
370
获赞
6
访问
27.2k
#include
using namespace std;
/*设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn。
问能否从这n件物品中选择若干件放入背包中,使得放入的重量之和正好为S。
如果有满足条件的选择,则此背包有解,否则此背包问题无解。
算法思想是划分子问题,对于背包数组里的每个元素,有两种可能:
1.当前元素在最后成功的组里,即剩余的元素中有组合为(s-当前元素的值)的情况;
2.当前元素不在,则继续判断剩余元素;
举个例子:s=20,w[5]={1,3,5,7,9}
从9开始判断:9在yes序列中的情况,则判断s=20-9=11,w[4]={1,3,5,7}递归下去;
9不在,直接判断s=20,w[4]={1,3,5,7}递归下去。*/
int bag(int s,int n,int w[]){
if(s==0) return 1;
if(n==0&&s!=0) return 0;
int high=n-1;
if(bag(s-w[high],n-1,w))//当前元素在成功组里
return 1;
else if(bag(s,n-1,w))//当前元素不在成功组,但有别的成功组
return 1;
else return 0;//不存在
}
int main(){
int s;int n;
while(cin>>s>>n){
int w[n];
for(int i=0;i cin>>w[i];
if(bag(s,n,w))//判断
cout <<"YES"< else cout<<"NO"<
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发