Question

一道C++题目求解

不同组合数求和

给你
n 个不等的正整数 a1，a2，a3，……，an，从中任取 m
个求和，这些和构成一个新的集合，请你计算新集合的元素个数。

输入：

两行，第一行包含一个正整数 n，第二行包含 n 个不等的正整数（依次为 a1，a2，a3，……，an），两两之间有一个空格分隔。

输出：

一个正整数

输入示例：

3
1 8 9

输出示例：

6

其他说明：

数据范围：0<m<=n<1000,1000>a1>a2>a3>……>an>0。
快快快快快！！！！

Answer 1

//注意到0<m<1000数量级小于 2^10  结果比较小 采用枚举法

#include<iostream>

using namespace std;

int result[1000],m;

int NextN(int N)//位运算

{

    return (N+(N&(-N))) | ((N^(N+(N&(-N))))/(N&(-N)))>>2;

}

int cal(int set[1000],int C)//枚举非空子集

{

    int i = 0;

    int res=0;

    int k;

    while((k=1<<i)<=C)

    {//循环测试每个bit是否为1

        if((C&k)!=0)

        {

            res=res+set[i];

        }

        i++;

    }

    for(i=0;i<m+1;i++)

        if(res==result[i])

            return 0;

    result[m]=res;

    m++;

    return 0;

}

void Subnum(int set[1000],int n)//枚举所有可能并计算

{

int i =1;

while (i<=n)

{

int c = (1<<i) -1; //c是每一组的第一个数

while (c<=(1<<n)-1)

{

cal(set,c);

c = NextN(c);

}

i++;

}

}

int main()

{

    int i;

    int num[1000];

    int n;

    cin>>n;

    for(i=0;i<n;i++)

        cin>>num[i];

    Subnum(num,n);

    cout<<m<<endl;

    return 0;

}

追问

我记得老师写的很短……

Answer 2

在栈上创建的对象是先创建的后析构，所以在这个程序中y(6,7)先析构，x(5)后析构。
析构一个对象时的顺序是：子类的析构函数->子类的成员变量->父类的析构函数->父类的成员变量。
创建y(6,7)，6赋值给了父类，7赋值给了子类的成员变量，所以输出是
Destructor B！7
Destructor A！6
创建x(5)时，5赋值给了父类，0赋值给了子类的成员变量，所以输出是
Destructor B！0
Destructor A！5

Answer 3

#include<iostream>
using namespace std;
int n,a,s,ans;
bool x[10001];
int main()
{
    scanf("%d",&n);
    x[0]=1;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        s+=a;
        for(int j=s;j>=0;j--) if(x[j]) x[j+a]=1;
    }
    for(int i=1;i<=s;i++) if(x[i]) ans++;
    printf("%d",ans);
    return 0;
}