www.pudn.com > zhongweishu.rar > 算法作业.txt, change:2017-04-14,size:1104b


#include<iostream> 
using namespace std; 
int MaxWeight(int w[],int c); 
int MaxValue(int w[],int v[],int n,int c); 
int main() { 
	int n, c,i; 
	cout << "请输入物品的数量:" << endl; 
	cin >> n; 
	cout << "请输入所能装的物品的最大重量:" << endl; 
	cin >> c; 
	int *a = new int[n]; 
	int *b = new int[n]; 
	cout << "请按照顺序输入各个物品的重量:" << endl; 
	for (i = 0; i < n; i++) { 
		cin >> a[i]; 
	} 
	cout << "请按照顺序输入各个物品的价格:" << endl; 
	for (i = 0; i < n; i++) { 
		cin >> b[i]; 
	} 
	cout << MaxValue(a, b, n, c); 
} 
int MaxValue(int w[], int v[], int n, int c) { 
	int i, j; 
	int **V; 
	V = new int *[n + 1]; 
	for (int i = 0; i < n+1; i++) { 
		V[i] = new int[c + 1]; 
	} 
	for (i = 0; i <= n; i++) { 
		V[i][0] = 0; 
	} 
	for (j = 0; j <= c; j++) { 
		V[0][j] = 0; 
	} 
	for (i = 1; i <= n; i++) { 
		for (j = 1; j <= c; j++) { 
			if (j < w[i]) { 
				V[i][j] = V[i - 1][j]; 
			} 
			else { 
				if (V[i - 1][j] >= V[i - 1][j - w[i]] + v[i]) { 
					V[i][j] = V[i - 1][j]; 
				} 
				else { 
					V[i][j] = V[i - 1][j - w[i]] + v[i]; 
				} 
			} 
		} 
	}return V[n][c]; 
}