0-1问题

输入两个整数n和m，从数列1,2,3,…,n中随意取数，使其和等于m，要求将其中所有可能的组合列出来。

 

这是一个0-1背包问题。有一个体积为m的箱子，有1-n体积的物体n个，求填充方法。

 

 

#include <iostream>
#include <string>
using namespace std;
int mVal,nVal;
int *pOut; //箱子，即数组，初始化为0，为1表示取箱子

int sum=0; //解法计数

void output()
{
    cout<<"第"<<sum<<"解法： ";
    for(int i=1; i<=nVal; i++)
        if(pOut[i])
            cout<<i<<' ';
    cout<<endl;
}

//m——剩余体积，n——剩余的最大物品体积

void find(int m, int n)
{
    if(m<1 || n<1 || (1==n)&&(m>1))
        return;
    if(m==n)
    {
        pOut[n]=1;
        sum++;
        output();
        pOut[n]=0;
    }
    find(m, n-1); //不取n

    pOut[n]=1; //取n

    find(m-n, n-1);
    pOut[n]=0;
}

void main()
{
    cout<<"请输入m: ";
    cin>>mVal;
    cout<<"请输入n: ";
    cin>>nVal;
    if(mVal < nVal) //如果mVal
        nVal=mVal;
    pOut = new int[nVal+1];
    memset(pOut, 0, (nVal+1)*sizeof(int)); //将pOut指示的大小为((nVal+1)*sizeof(int))的内存空间初始化为0，memset以字节为单位

    find(mVal, nVal);
    delete []pOut;
}