注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

和申的个人主页

专注于java开发,1985wanggang

 
 
 

日志

 
 

子集和问题--回溯算法  

2008-11-14 21:45:15|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题描述 :
子集和问题的一个实例为〈S,t 〉。其中,S={ X1 ,X2 ,…,Xn } 是一个正整数的集合,C是一个正整数。子集和问题判定是否存在S 的一个子集S1 ,使得∑X (X∈S1) = C。
编程任务 :
对于给定的正整数的集合S={ X1 ,X2 ,…,Xn } 和正整数C,编程计算S 的一个子集S1 ,使得∑X (X∈S1) = C。
数据输入 :
有m组输入数据,第1 行是m的个数,接下来是m组数据,每组数据有两行组成,第1行是2个正整数n(n<400)和c,n表示S的大小,c是子集和的目标值。接下来的1行中,有n个正整数,表示集合S中的元素 。
结果输出:
输出有m行,每行是子集和问题的解输出,当问题无解时,输出“No Solution!”。
输入样例:
    2
    5 10
    2 2 6 5 4
    5 3
    2 2 6 5 4
输出样例:
    2 2 6
    No Solution!

/**

wanggang 2008.11.14 采用回溯法,遍历二叉树,有待改进,加入限制函数,和界限函数,而且 输出的文件也可以只打开一次

在c:\\盘下建立input.txt文件输出文件result.txt也在c盘下

##c:\\input.txt

在Dev c++ IDE下编译通过

***/

#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
int len;
int sumRemain;
int currentSum=0;
int sum;
int data[400];
int x[400];

void GetInput(istream&fin)
{
 int i,j;
 //ifstream fin("c:\\input1.txt");
   
 

 fin>>len;//数据长度
 fin>>sum;//目标和
 for(i=1;i<=len;i++)
 {
     fin>>data[i];
 }
 cout<<"there are"<<len<<" numbers"<<endl;//测试数据的个数
    cout<<"the sum is "<<sum<<endl;
 

 
}
void saveResult(){//保存符合条件的结果
     ofstream fout( "c:\\results.txt", ios::app );//追加模式
     for(int j=1;j<=len;j++) {                  
           if(x[j] ==1){
                 fout<<data[j]<<" ";//输出结果
           }
     }
     fout<<endl;
     fout.close();
}
void backtrack(int i)//整个函数采用遍历整个二叉树,搜索出符合条件的结果 ,将所有符合要求的解全部显示出来
{
     cout<<"in backtrack("<<i<<")"<<endl;
     if(i>len)
     {
      for(int j=1;j<=len;j++) {                  
           cout<<x[j];//输出路径
      }
            cout<<endl;
         cout<<" >len"<<endl;
         cout<<" currentSum"<<currentSum<<endl;
          if(currentSum ==sum)//符合条件
          {
            cout<<"get result "<<endl;
            for(int j=1;j<=len;j++) {                  
                    if(x[j] ==1){
                            cout<<data[j]<<" ";//输出结果
                    }
            }
             cout<<endl;
             saveResult();//保存结果到文件
           
          }
         
          return ;
          
     }
    
    
     if(currentSum+data[i]<=sum)//左子树 ,当前的加和没有超过sum
     {
     cout<<"int left "<<i<<"层 "<<data[i];
          x[i] =1;currentSum +=data[i];
          cout<<" currentSum="<<currentSum<<endl;
       backtrack(i+1);//深度优先遍历 ,进入 子树
          currentSum -=data[i];
           cout<<"int left back "<<i<<"层 "<<currentSum<<endl;   
     }
      //右子树
      cout<<"in rigth"<<i<<"层 "<<data[i]<<" currentSum="<<currentSum<<endl;
      x[i]=0;
      backtrack(i+1);//深度优先遍历 ,进入 子树
    
   
     return ;
}

int main(int argc, char *argv[])
{
    ifstream fin("c:\\input.txt");
    int m;
    fin>>m;//m组数据
    for(int i=0;i<m;i++){
        GetInput(fin);//从文件输入 数据 获得len ,sum ,data等数据
        backtrack(1);//调用  注意是从1 开始到len 结束
        cout<<"----------------------"<<endl;
        ofstream fout( "c:\\results.txt", ios::app );//追加模式
        fout<<"----------------------"<<endl;
        fout.close();
    }
    fin.close();
    system("PAUSE");
    return EXIT_SUCCESS;
}

 

修改版2008.11.16================================================================

==============================================================================

#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
int len;
int sumRemain;
int currentSum=0;
int sum;
int data[400];
int x[400];
int remainSum;

void GetInput(istream&fin)
{
 int i,j;
 //ifstream fin("c:\\input1.txt");
   
 

 fin>>len;//数据长度
 fin>>sum;//目标和
 for(i=1;i<=len;i++)
 {
     fin>>data[i];
     remainSum+=data[i];
 }
 cout<<"there are"<<len<<" numbers"<<endl;//测试数据的个数
    cout<<"the sum is "<<sum<<endl;
 

 
}
void saveResult(){//保存符合条件的结果
     ofstream fout( "c:\\results.txt", ios::app );//追加模式
     for(int j=1;j<=len;j++) {                  
           if(x[j] ==1){
                 fout<<data[j]<<" ";//输出结果
           }
     }
     fout<<endl;
     fout.close();
}
void backtrack(int i)//整个函数采用遍历整个二叉树,搜索出符合条件的结果 ,将所有符合要求的解全部显示出来
{
     cout<<"in backtrack("<<i<<")"<<endl;
     if(i>len)
     {
      for(int j=1;j<=len;j++) {                  
           cout<<x[j];//输出路径
      }
            cout<<endl;
         cout<<" >len"<<endl;
         cout<<" currentSum"<<currentSum<<endl;
          if(currentSum ==sum)//符合条件
          {
            cout<<"get result "<<endl;
            for(int j=1;j<=len;j++) {                  
                    if(x[j] ==1){
                            cout<<data[j]<<" ";//输出结果
                    }
            }
             cout<<endl;
             saveResult();//保存结果到文件
           
          }
         
          return ;
          
     }
     remainSum-=data[i];
    
     if(currentSum+data[i]<=sum)//左子树
     {
     cout<<"int left "<<i<<"层 "<<data[i];
          x[i] =1;currentSum +=data[i];
          cout<<" currentSum="<<currentSum<<endl;
       backtrack(i+1);//深度优先遍历 ,进入 子树
          currentSum -=data[i];
           cout<<"int left back "<<i<<"层 "<<currentSum<<endl;   
     }
     if(  remainSum + currentSum >=sum){//如果剩余的数的和当前的总和大于目标和就继续运算,否则,不满足条件就剪掉该枝
      //右子树
      cout<<"in rigth"<<i<<"层 "<<data[i]<<" currentSum="<<currentSum<<endl;
      x[i]=0;
      backtrack(i+1);//深度优先遍历 ,进入 子树
  }
    remainSum+=data[i];
     return ;
}

int main(int argc, char *argv[])
{
    ifstream fin("c:\\input.txt");
    int m;
    fin>>m;//m组数据
    for(int i=0;i<m;i++){
        GetInput(fin);//从文件输入 数据 获得len ,sum ,data等数据
        backtrack(1);//调用  注意是从1 开始到len 结束
        cout<<"----------------------"<<endl;
        ofstream fout( "c:\\results.txt", ios::app );//追加模式
        fout<<"----------------------"<<endl;
        fout.close();
    }
    fin.close();
    system("PAUSE");
    return EXIT_SUCCESS;
}

 

注:回溯算法

  评论这张
 
阅读(5654)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016