动态规划解决0-1背包问题

#include<iostream>
using namespace std;
#include<stdio.h>

template <class Type>
Type min(Type a,Type b){
	return a > b ? b:a;
}

template <class Type>
Type max(Type a,Type b){
	return a < b ? b:a;
}

template <class Type>
void Knapsack(Type *v,int *w,int c,int n,Type **m){
	int jMax = min(w[n] - 1,c);
	for(int j = 0;j <= jMax;j++)m[n][j] = 0;
	for(j = w[n];j <= c;j++)m[n][j] = v[n];
	for(int i = n-1;i > 1;i--){
		jMax = min(w[i]-1,c);
		for(j = 0;j <= jMax;j++)
			m[i][j] = m[i+1][j];
		for(j = w[i];j <= c;j++)
			m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
	}
	m[1][c] = m[2][c];
	if(c >= w[1])
		m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);
}

template<class Type>
void Traceback(Type **m,int *w,int c,int n,int *x){
	for(int i = 1;i < n;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 main(){
	int num,c;
	cout<<"输入物品数目和背包最大容量：";
	cin>>num>>c;

	int *v = (int *)malloc((num+1) *sizeof(int));//价值数组
	int *w = (int *)malloc((num+1) *sizeof(int)); //重量数组

	cout<<"\n输入每个物品的价值和重量：\n";
	for(int i = 1;i <= num;i++)
		cin>>v[i]>>w[i];

	int ** m = (int **)malloc((num+1) * sizeof(int*));
	for(i = 1;i <= num;i++)
		m[i] = (int*)malloc((num+1) *sizeof(int));

	int *x = (int *)malloc((num+1) *sizeof(int));//记录物品是否放入背包

	Knapsack(v,w,c,num,m);
	Traceback(m,w,c,num,x);

	cout<<"装入的物品为：\n";
	for(i = 1;i <= num;i++)
	{
		if(x[i])
		cout<<i<<" ";
	}
	cout<<"背包现在的价值为："<<m[1][c]<<endl;

}