作者：解学武

本节解决如下一个背包问题：
设：有一个背包可以放入的物品重量为 t。现有 n 件物品，重量分别为：w₁、w₂、…w_n。问题是：能够从这 n 件物品中选择若干件放入此背包，使得放入的重量之和正好为 t。如果存在一种符合上述要求的选择，则称此背包问题有解，否则此问题无解。

例如，t=10，n=5，w[5]={1,4,4,5,7}，则此背包问题有解：

1. 方案 1 为：向背包中放入 w[0]、w[1] 和 w[3]；
2. 方案 2 为：向背包中放入 w[0]、w[2] 和 w[3]；

提示：虽然 w[1] 和 w[2] 物品重量相同，但其不是同一件物品，所以会产生以上两种方案。

解题思路

可以使用递归思想解决此问题：用 knap(w,t,n) 表示上述背包问题的解。这个函数返回的值要么为 1（表示解为真），要么为 0（表示解为假），同时其参数应满足 t 大于等于 0 ，且 n 大于等于1 。

背包问题如果有解，其选择只可能有两种可能：

• 选择的一组物品中不包含 w_n，这样 knap(w,t,n) 的解就是 knap(w,t,n-1)的解；
• 选择的一组物品中包含 w_n，这样 knap(w,t,n) 的解就是 knap(w,t-w_n,n-1)的解。

另外，递归的出口有以下几种情况：

• 若 t 的值为0，则说明背包问题总有解，即 knap(w,0,n) = 1，不选择任何物品进入背包；
• 若 t 的值小于0，则背包问题肯定无解，即knap(w,t,n) = 0，因为无论怎样选择也不能使重量之和为负值；
• 若 t 的值大于0，但 n 的值小于 1，此种情况背包问题也无解，即 knap(w,t,n) =0，因为不取任何东西却要使重量为正值，其本身是矛盾的。

所以，此种方法的实现代码为：

#include <stdio.h>

int knap(int w[],int t,int n){
    //递归出口，当 t=0时，背包问题有解
    if(t==0){
        return 1;
    }
    else{
        //递归出口，符合 t<0 或 t>0同时 n<1 时，背包问题无解
        if(t<0 || (t>0 &&n<1) ){
            return 0;
        }
        //如果以上情况都不是，则可能有解
        else{
            //选择一组物件包含 wn，如果最终结果为 1，则输出可能的一种解
            if(knap(w,t-w[n-1],n-1)==1){
                printf("result:n=%d,w[%d]=%d\n",n,n-1,w[n-1]);
                return 1;
            }else{
                //选择一组物件中不包含wn
                return knap(w,t,n-1);
            }
        }
    }
}

int main(){
    int w[5] = {1,4,4,5,7};
    int n = 5;
    int t = 10;
    knap(w,t,n);
    return 0;
}

运行结果：

此算法不足之处在于：如果背包问题有多种解，则使用该程序就只能输出一种。

为了能够输出所有解，我们可以将递归算法改为用栈实现的非递归算法。具体思路是：设置一个栈，用来存放加入背包的物品序号，若某一时刻栈中物品的总重量恰好等于背包要求容纳的重量，则此为一个解。

利用栈的特点，可以输出此背包问题的所有解，其实现代码为（有详细注释）：

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;//栈中存放数据的类型
typedef struct{
    ElemType data[MAXSIZE];//栈空间
    int top;//栈顶指针
}SqStack;
//初始化栈
void Init_SqStack(SqStack * S){
    S->top = -1;
}
//判断栈是否为空
int Empty_SqStack(SqStack * S){
    if(S->top ==-1){
        return 1;
    }
    return 0;
}
//将数据 x 进栈
void Push_SqStack(SqStack * S,ElemType x){
    //在 x 进栈之前，需要判断栈是否已满
    if(S->top == MAXSIZE-1){
        printf("栈满");
        exit(0);
    }else{
        S->data[++S->top]=x;
    }
}
//弹栈，并将弹出的数据赋值给 x
void Pop_SqStack(SqStack *S,ElemType *x){
    if(Empty_SqStack(S)){
        printf("栈空");
        exit(0);
    }else{
        *x = S->data[S->top];
        S->top--;
    }
}
//背包问题处理函数
int knap(int w[],int t,int n){
    SqStack S;
    int j,k;
    Init_SqStack(&S);
    k =0;//表示几号物品
    do{//从 0 号物品开始判断
        while(t>0 && k<n){
            if(t-w[k] >= 0){
                Push_SqStack(&S,k);
                t-=w[k];
            }
            k++;
        }
        //如果此时 t 为 0，证明栈中存放的数据为背包问题的一个解
        if(t==0){
            printf("result:\n");
            for(j=0; j<=S.top;j++){
                printf("n=%d,w[%d]=%d\n",S.data[j]+1,S.data[j],w[S.data[j]]);
            }
        }
        //回溯去寻找下一个解
        Pop_SqStack(&S,&k);
        //弹出一个物品，其背包的剩余重量需要增加
        t+=w[k];
        k++;
    }while(!Empty_SqStack(&S) || k != n);
}
int main(){
    int w[5]={1,4,4,5,7};
    int n = 5;
    int t = 10;
    knap(w,t,n);
    return 0;
}

运行结果：
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。