备忘录法解背包问题,代码哪里错了额。。

#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");
	}

}
 

全部评论
递归没出口 int MFKnapsack( int i , int j , struct Knapsack *knapsack , struct Goods *goods ) { int value ; if(i==0) return 0 ; else { 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] ; } }
点赞 回复 分享
发布于 2015-12-16 13:31

相关推荐

10-05 23:02
东北大学 Java
我说句实话啊:那时候看三个月培训班视频,随便做个项目背点八股,都能说3 40w是侮辱价
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务