01beibao.txt

来自「算法与数据结构——快速排序 01背包问题,是一个简单的程序,高手就不用研究了」· 文本 代码 · 共 27 行

public static void knapsack(int []V,int []W,int c, int [][]m)
{	int n=v.length-1;
	int jMax=Math.min(w[n]-1,c);  //最后一个物品的重量与C的小者
	for(int j=0;j<=jMax;j++)
		m[n][j]=0;
	for(int j=w[n];j<=c;j++)
		m[n][j]=v[n];

	for(int i=n-1;i>1;i--){
		jMax=Math.min(w[i]-1,c);
		for(int j=0;j<=jMax;j++)
			m[i][j]=m[i+1][j];
		for(int j=w[i];j<=c;j++)
			m[i+1][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
		}
	m[i][c]=m[2][c];
	if(c>=w[1])
		m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);

}

n=3，c=6，w={4，3，2}，v={5，2，1}。
jmax=2
m[3,0]  m[3,1]  m[3,2]  m[3,3] m[3,4] m[3,5] m[3,6]
0        0       1        1       1     1      1