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