【说明】

0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1...i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。

0-1背包问题具有最优子结构性质。定义c[i][T]为最优装包方案所获得的最大价值，则可得到如下所示的递归式。



【c代码】

下面是算法的C语言实现。

(1) 常量和变量说明

T: 背包容量

v[]:价值数组

w[]:重量数组

c[][]:c[i][j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值



(2) C程序

本人将不方便阅读的图片梳理成文字

#include 
#include 
#define N6
#define maxT 1000
int c[N][maxT]= {
	0
}
;
int Memoized_Knapsack(int v[N],int w[N],int T) {
	int i;
	int j;
	for (i=0; i
	for (j=0; j<=T; j++) {
		c[i][f]= -1;
	}
}
return Calculate_Max_Value(v, w, N-1, T);
}
int Calculate_Max_Value(int v[N],int w[N], int i, int j) {
int temp =0;
if (c[i][j]!=-1) {
	(1)
}
if (i==0||j==0) {
	c[i][j]=0;
} else {
	c[i][j]=Calculate_Max_Value(v, w, i-1, j);
	if( (2) ) {
		temp=(3) ;
		if(c[i][j]
		(4)
	}
}
}
return c [i][j];
}