高手请进--写一算法

等待高手贡献

iwillwin

up

lixiubing

关注

gupaladin

18种吧？不知道对不对，不过不是程序算的，我手工算的，汗一个，组合数学！

dreamer_2002

0/1 knapsack problem
subset sum problem

opky

这个问题，课本上有解答。好象是 清华 王晓东

dreamer_2002

0/1 背包问题分为：
0-1 Equality Knapsack Problem 和 0-1 inequality Knapsack Problem
0-1 inequality Knapsack Problem 求最优， 算法较多
0-1 Equality Knapsack Problem 求恰好装满的情况数， 我还没找到比较公认的有效算法
如有， 贴出来共享一下，我最近也在看算法

KANKANWO

顶一下

tang2007

关注一下！

medie2005

这个好解。可以用动态规划求解。

如果是：一个组合里的元素不重复的情况的话，代码如下：

#include <stdio.h>
#include <gmp.h>

void  f( int Max )
{
        int i, j;
        mpz_t  *list=new mpz_t[ Max+1 ];
        for( i=0; i<=Max; ++i )
                mpz_init( list[ i ] );
        mpz_set_ui( list[ 0 ],1 );

        for( i=1; i<=Max; ++i ){
                j=Max-i;
                while(j>=0)
                        mpz_add( list[ i+j ],list[ i+j ],list[ j-- ] );
        }
        mpz_out_str( stdout,10,list[ Max ] );
        printf("\n";
        delete [ ]list;
}

int  main(  )
{
        int n;
        scanf("%d",&n);
        f( n );
        return 1;
}

由于当n=10000时，满足条件的组合个数很多，大大超出了__int64的表示范围，因此，代码中使用了大数运算库GMP，需要GMP的可以发邮件到medie2006@126.com。

n=10000时，
运行结果是：1122606574548038398976040173670530159089991444775125551802871247408332723840