阅读:0       作者:严长生

背包问题详解(带源码+解析)

本节解决如下一个背包问题:
设:有一个背包可以放入的物品重量为 t。现有 n 件物品,重量分别为:w1、w2、…wn。问题是:能够从这 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 。

背包问题如果有解,其选择只可能有两种可能:
  • 选择的一组物品中不包含 wn,这样 knap(w,t,n) 的解就是 knap(w,t,n-1)的解;
  • 选择的一组物品中包含 wn,这样 knap(w,t,n) 的解就是 knap(w,t-wn,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;
}
运行结果:
result:n=1,w[0]=1
result:n=3,w[2]=4
result:n=4,w[3]=5

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

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


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

#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;
}
运行结果:
result:
n=1,w[0]=1
n=2,w[1]=4
n=4,w[3]=5
result:
n=1,w[0]=1
n=3,w[2]=4
n=4,w[3]=5