1146subset of several questions.cpp

来自「子集和数问题 实现对图的最小生成树实现」· C++ 代码 · 共 83 行

#include <iostream>
using namespace std;
#include <stdio.h>
int len; 
int sum; 
int data[100000]; // 数据.
char output[100000]; // 所求子集元素，与输入数据对应，'Y'为取.
void GetInput(){ 
    int i;
	cin >> len >> sum ;
    for(i = 0; i < len; i++){
	scanf("%d", &data[i]);
        output[i] = 'N';
    }
}
int GetRes(){
    int p = 0; // 指向当前值.
    int temp = 0; // 当前子集合和.
    while(p >= 0){
        if('N' == output[p]){
            // 选中当前项.
            output[p] = 'Y';
            temp += data[p];
            if(temp == sum){
                return 1;
            }
            else if(temp > sum){
                output[p] = 'N';
                temp -= data[p];
            }
            p++;
        }
        if(p >= len){
            while('Y' == output[p-1]){
                p--;
                output[p] = 'N';
                temp -= data[p];
                if(p < 1){
                    return 0;
                }
            }
            while('N' == output[p-1]){
                p--;
                if(p < 1){
                    return 0;
                }
            }
            output[p-1] = 'N';
            temp -= data[p-1];
        }
    }
    return 0;
}
void PrintRes(){
    int i ;
    for(i = 0; i < len; i++)
	{
        if('Y' == output[i])
		{
          // best[k]=data[i];
          cout<<data[i]<<" ";
		  // k++;
        }
    }
	cout<<endl;
//	for( i = 0 ; i < k-1 ; i ++ )
	//cout << best[i] << " ";
	//cout<<best[i]<<endl;
}
int main()
{
		GetInput();
      if(GetRes())
	  {
        PrintRes();
	  }
      else
	  {
        cout<<"No Answer"<<endl;
      }	
	return 0;
}