上次记录了，0/1背包问题动态规划的递归实现，下面记录一下也是动态规划的非递归实现。主要是对f函数结果的记录，使得不用像递归中的重复计算。

#include<stdio.h>
#include<stdlib.h>

#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define N 3
#define C 116

int p[N+1];
int w[N+1];
int f[N+1][C+1];
int x[N+1];
void bag(){
    int y,ymax,i;

    ymax=min(w[N]-1,C);
    for(y=0;y<ymax;y++)
        f[N][y]=0;
    for(y=w[N];y<C;y++)
        f[N][y]=p[N];

    for(i=N-1;i>1;i--){
        ymax=min(w[i]-1,C);
        for(y=0;y<ymax;y++)
            f[i][y]=f[i+1][y];
        for(y=w[N];y<C;y++)
            f[i][y]=max(f[i+1][y],f[i+1][y-w[i]]+p[i]);
    }
    f[1][C]=f[2][C];
    
    if(C>w[1])
        f[1][C]=max(f[2][C],f[2][C-w[1]]+p[1]);
}

void traceback(){
    int i,c;
    
    c=C;
    for(i=1;i<N;i++)
        if(f[i][c]==f[i+1][c])
            x[i]=0;
        else{
            x[i]=1;
            c-=w[i];
        }
        x[N]=(f[1][C])?1:0;
    }

int main(){
    w[1]=100;
    w[2]=14;
    w[3]=10;
    p[1]=20;
    p[2]=18;
    p[3]=15;
    bag();
    printf("the max :%d\n",f[1][C]);
    traceback();
    int i;
    for(i=1;i<=N;i++)
        printf("%d ",x[i]);
    printf("\n");
    return 0;
}
    

时间复杂度：bag是：O（nc)。如果c很大，则时间要比递归的长。