简单背包问题-递归非递归实现

Thereisnospon 2021-08-13 原文

递归实现

#include<stdio.h>
#define MAX 100
int w[MAX]={0,1,2,3,4,5};
int ans(int s,int m)
{
    int s1,b,i;
    if(s==0)return 1;
    else if(s<w[0]||m<0)return 0;
    else
    {
        for(i=m;i>=0;i--)
        {
            s1=w[i];
            b=ans(s-s1,i-1);
            if(b==1)break;
        }
        if(!b)return 0;
        else
        {
            printf("%d\n",s1);
            return 1;
        }
    }
}

非递归实现

int Ans(int s,int m)
{
    typedef struct
    {
        int s;
        int m;
    }stacknode;
    stacknode stack[MAX];
    int i,j,t,top,nofail;
    t=0;top=0;nofail=1;//i为当前已选择的重量，nofail为还无法确认求解失败
    while(s!=t&&nofail)//当还没有选择足够重量并且无法确认失败时
    {
        if(s>=t+w[1]&&m>0)//至少还能选择一个物品
        {
            stack[top].s=w[m];//选择该物品，并将其入栈
            stack[top].m=m;
            top++;
            t=t+w[m];//当前重量更新
            
            m--;//接着下一个物品
        }
        else
        {
            if(m==0)//刚才一个选择不合适，需要回溯
            {
                top--;
                t=t-stack[top].s;
            }
            if(top<1)nofail=0;//栈空，判断失败
            else//栈顶元素选择不合适，从其前一个元素开始重新选择
            {
                top--;
                m=stack[top].m-1;
                t=t-stack[top].s;
            }
        }
    }
    if(s==t)
        for(i=0;i<top;i++)
        printf("%d\n",stack[i].s);
}