文章

3

粉丝

370

获赞

6

访问

27.3k

头像
背包问题:简单递归思想(也可写成动态规划)
推荐阅读
P1035
发布于2021年1月10日 23:16
阅读数 9.8k

#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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发