01背包问题算法源码（C++）

01背包问题算法的C++实现。 knapsack.cpp + knapsack.h

#include “knapsack.h“

#include 
#include 
#include 
#include 


void knapsack（int v[]int w[] int cint n int**m） 
{ 
	int jmax = std::min（w[n]-1c）; 

	for（int j=0;j<=jmax;j++） 
		m[n][j]=0; 
	for（int jj=w[n];jj<=c;jj++） 
		m[n][jj]=v[n]; 
	for（int i=n-1;i>1;i--）	// recursive O（nc）
	{ 
		jmax = std::min（w[i]-1 c）; 
		for（int j = 0;j <= jmax;j++） 
			m[i][j] = m[i+1][j]; 
		for（int jj = w[i];jj <= c; jj++） 
			m[i][jj] = std::max（m[i+1][jj] m[i+1][jj-w[i]]+v[i]）; 
	} 
	m[1][c] = m[2][c]; 

	if（c>=w[1]） 
		m[1][c] = std::max（m[1][c] m[2][c-w[1]]+v[1]）;			// m[1][c] maximum value

} 

void traceback（int **mint w[]int cint nint x[]） 
{ 
	for（int i=1;i		if（m[i][c]==m[i+1][c]） x[i]=0; 
		else {x[i]=1; 	c-=w[i];} 

	x[n]=（m[n][c]）?1:0; 
} 

void printx（ const int n const int c int* x int** m ）
{
	std::cout<<“最优解：“<	for （int j = 1; j < n+1; j++）
	{
		std::

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        655  2011-08-27 09:13  knapsack.h

     文件       1927  2011-10-31 21:18  knapsack.cpp

----------- ---------  ---------- -----  ----

                 2582                    2