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

#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

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务