背包问题.cpp

背包问题的c++描述

#include <iostream>

using namespace std;

int max(int a, int b)
{
	return a >= b ? a : b;
}

int main()
{
    int i, j;
	int N, C;//输入数量和容量
	cin >> N >> C;
	int **a = new int *[N+1];
	for(i = 0; i <= N; i++)
		a[i] = new int[C+1];
	int *b, *v;
	b = new int[N+1];//占的容量
	v = new int[N+1];//价值
	for(i = 1; i <= N; i++)
		cin >> b[i] >> v[i];
	for(i = 0; i <= N; i++)//初始化
		a[i][0] = 0;
	for(i = 0; i <= C; i++)
		a[0][i] = 0;
	
	for(i = 1; i <= N; i++)
		for(j = 1; j <= C; j++)
		{
			a[i][j] = a [i-1][j];
			if(b[i] <= j)
				a[i][j] = max(a[i][j], a[i-1][j-b[i]] + v[i]); 
		}
	for(i = 1; i <= N; i++)
	{	
		for(j = 1; j <= C; j++)
			cout << '\t' << a[i][j];
		cout << endl;
	}
	cout << "最优解是" << a[N][C] <<endl;
	for(i = 0; i <= N; i++)
    {
		delete [C+1]a[i];
        a[i] = NULL;
    }
    delete [N+1]a;
    a=NULL;

    return 0;
}