程序代码：

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

#define  MaxNumber 100
#define  MaxWeight1 100
int M[100][100],T[100][100] ;
int book[100] ;

struct Goods
{
    int    weight[ MaxNumber ] ;
    int value[ MaxNumber]   ;
    int numbers            ;//物品数量
} ;


struct Knapsack
{
    int MaxWeight ;  //背包承重量

} ;

int Max( int a, int b )
{
    if(a>b) return a ;
    else return b ;
}


//自底向上动态规划
int MaxValue( struct Knapsack *knapsack ,  struct Goods *goods )
{
    int i , j ;

    for(j=0 ; j<=knapsack->MaxWeight ; j++ ) //第0行每列都为0
        M[0][j] = 0 ;   

    for(i=1 ; i<=goods->numbers ; i++)
    {
        M[i][0] = 0  ;    //逐行，从左向右依次填充表格
        for(j=1 ; j<= knapsack->MaxWeight ; j++)
        {
            if( j< goods->weight[i] )
                M[i][j] = M[i-1][j] ;
            else  
                M[i][j] = Max( M[i-1][j] , goods->value[i]+M[i-1][ j-goods->weight[i] ] ) ;            
        }    
    }
    
    return M[goods->numbers][knapsack->MaxWeight] ;
}

//动态规划：备忘录法
//改动变化原因
int  MFKnapsack( int i , int j , struct Knapsack *knapsack ,  struct Goods *goods ) 
{
    int value ;
    if(i>=0&&j>=0)
    {
        if(T[i][j]<0)
        {
            if( j<goods->weight[i] )
                value = MFKnapsack(i-1,j, knapsack ,  goods ) ;
            else
                value =  Max(   MFKnapsack(i-1,j, knapsack , goods ) ,
                           goods->value[i]+MFKnapsack( i-1 , j-goods->weight[i] , knapsack , goods )  );
            T[i][j] = value ;
        }
        
        return T[i][j] ;
    }
    
}


void recall(struct Knapsack *knapsack ,  struct Goods *goods )
{
    int i , j ;//回溯表格，标记最优子集中的物品,属于最优子集中的标记为1，否则标记为0
    j=knapsack->MaxWeight ;
    for(i=goods->numbers ; i>=0 ; i--)    
            if(M[i][j] == M[i-1][j] )
            {
                book[i]=0 ;//第i个物品放与不放不影响价值，则不需要放入
            }
            else
            {    
                book[i]=1 ;//第i个物品取出
                j = j-goods->weight[i] ;
            }
        
}

int main( )
{
    int i,j ;
    int MV ;
    struct Knapsack *knapsack ;
    struct Goods *goods ;

    knapsack=(struct Knapsack *)malloc(sizeof(struct Knapsack) ) ;
    goods = (struct Goods *)malloc( sizeof(struct Goods) ) ;

    printf("输入背包最大承重量\n");
    scanf( "%d" , &knapsack->MaxWeight ) ;//输入背包最大承重量

    printf("输入物品数量\n");
    scanf( "%d" , &goods->numbers ) ; //输入物品数量

    printf("输入物品重量\n");
    for( i=1 ; i<=goods->numbers ; i++ )//输入物品重量
    {
        scanf("%d",&goods->weight[i]) ;
    }

    printf("输入物品价值\n");
    for( i=1 ; i<=goods->numbers ; i++ )//输入物品价值
    {
        scanf("%d",&goods->value[i]) ;
    }

    MV=MaxValue( knapsack , goods ) ;

    printf("背包能容纳的最大价值%d\n" , MV ) ;    
    
    printf("输出表格\n");
    for(i=0 ; i<=goods->numbers ; i++)//输出表格
    {    
        for(j=0 ; j<=knapsack->MaxWeight ; j++)
            printf("%d ", M[i][j]) ;
        printf("\n");
    }
    
    //最优子集不止一种如何输出
    recall( knapsack , goods ) ;
    printf("输出最优子集物品编号\n") ;

    for(i=1;i<=goods->numbers;i++)
        if(book[i]==1) printf("%d ",i) ;
    printf("\n") ;

    //动态规划备忘录法
    //初始化表格
    for(i=0 ; i<=goods->numbers ; i++)
        for(j=0 ; j<=knapsack->MaxWeight ; j++)
            T[i][j] = -1 ; 
    MFKnapsack(goods->numbers ,  knapsack->MaxWeight , knapsack ,  goods ) ;

    for(i=0 ; i<=goods->numbers ; i++)//输出表格
    {    
        for(j=0 ; j<=knapsack->MaxWeight ; j++)
            printf("%d ", T[i][j]) ;
        printf("\n");
    }

}

[此贴子已经被作者于2015-12-16 08:22编辑过]

程序代码：

int MFKnapsack(int i, int j, struct Knapsack *knapsack, struct Goods *goods)
{
    int value;

    if (i > 0 && j > 0)
    {
        if (T[i][j] < 0)
        {
            if (j < goods->weight[i])
            {
                value = MFKnapsack(i - 1, j, knapsack, goods);
            }
            else
            {
                value = Max(MFKnapsack(i - 1, j, knapsack, goods),
                        goods->value[i] + MFKnapsack(i - 1, j - goods->weight[i], knapsack, goods));
            }
            T[i][j] = value;
        }
        return T[i][j];
    }
    return T[i][j] = 0;
}