背包问题的求解，有二道题

问题描述： 假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解： （1，4，3，2） （1，4，5） （8，2） （3，5，2）。 问题提示： 可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品"太大"不能装入，则弃之而继续选取下一件，直至背包装满为止。但如

#include
#include

int knap（int s int n int w[]） {
    if （ s == 0 ）
        return （1）;
    else if （ s<0 || s>0 && n<1 ）
        return（0）;
    else if （ knap（s - w[n-1] n - 1 w）==1 ） { 
        printf（“result: n=%d w[%d]=%d  \n“ n n-1 w[n-1]）;
        return （1）;
    }
    else
        return （ knap（s n - 1 w） ）;
}

int main（） {
    int* w;
    int s = 0 n = 0 result = 0 i = 0;
    printf（“please  input s = “）;/*输入s*/
    scanf（“%d“ &s）;
    printf（“please  input n = “）;/*输入n*/
    scanf（“%d“ &n）;
    w = （int*）malloc（n*sizeof（int））;
    printf（“please input the %d numbers（weight）:\n“ n）;/*输入重量*/
    for （i = 0; i < n; i++）
        scanf（“%d“ w+i）;
    result = knap（s n w）;
    if （result == 0）
        printf（“no solutio

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1424  2011-06-22 14:21  Cpp1.cpp

     文件       1256  2011-06-22 14:05  数组.cpp

     文件       1513  2011-06-22 14:29  a5.cpp

     文件       3324  2011-06-23 01:04  a55.cpp

     文件        833  2011-06-22 14:48  a.cpp

----------- ---------  ---------- -----  ----

                 8350                    5