/** * @brief 0_1_Knapsack  dynamic programming  * @author An * @data  2013.8.28                                                                  **//*** @problem  * @0-1背包问题： /*    给定n种物品和一个背包, 物品i的重量为wi，其价值为vi, 背包的容量为c,/*    应如何选择装入背包的物品，使得装入背包中的物品的总价值最大?/*    注：在选择装入背包的物品时，对物品i只有两种选择，/*        即装入或不装入背包。不能将物品i装入多次，也/*        不能只装入部分的物品i。 /* /* 1. 0-1背包问题的形式化描述： /*    给定c>0, wi>0, vi>0, 0<=i<=n，要求找到一个n元的 /*    0-1向量(x1, x2, ..., xn), 使得： /*            max sum_{i=1 to n} (vi*xi),且满足如下约束： /*        (1) sum_{i=1 to n} (wi*xi) <= c /*        (2) xi∈{0, 1}, 1<=i<=n /* * @                                                                 **/#include 
    
     #define max( x, y ) ( x >= y ? x : y )using namespace std;void Knapsack( int *weight, double *value, int capacity, int n, bool *res, double **V );int main(){	int w[] = { 2, 2, 6, 5, 4 };	int v[] = { 6, 3, 5, 4, 6 };	int n = 5;	int *weight = new int[n];	double *value = new double[n];	for ( int i = 0; i < n; ++i )	{		weight[i] = w[i];		value[i] = v[i];	}	int capacity = 10;	// distribute memory	bool *res = new bool[n];	double **V = new double*[n + 1];	for ( int i = 0; i <= n; ++i )	{		V[i] = new double[capacity + 1];	}	Knapsack( weight, value, capacity, n, res, V );	cout << "the max value is: " << V[n][capacity] << endl;	cout << "the items in the knapsack is: ";	for ( int i = 0; i != n; ++i )	{		if ( res[i] )		{			cout << i + 1 << ", ";		}	}	cout << endl;	return 0;}void Knapsack( int *weight, double *value, int capacity, int n, bool *res, double **V ){	// initialize 0 row and 0 column	for ( int i = 0; i <= n; ++i )	{		V[i][0] = 0;	}	for ( int j = 0; j <= capacity; ++j )	{		V[0][j] = 0;	}	// calculate V[][]	for ( int i = 1; i <= n; ++i )	{		for ( int j = 1; j <=capacity; ++j )		{			if ( j < weight[i - 1] )			{				V[i][j] = V[i - 1][j];			}			else			{				V[i][j] = max( V[i - 1][j], V[i - 1][j - weight[i - 1]] + value[i - 1] );			}		}	}	int j = capacity;	for ( int i = n; i > 0; --i )	{		if ( V[i][j] > V[i - 1][j] )		{			res[i - 1] = true;			j -= weight[i - 1];		}		else		{			res[i - 1] = false;		}	}}