学步园

一道经典dp

一开始就想递推。。。后来发现就过了三个点。。

于是乎搬来了这种01背包的模板。AC了、

代码略丑。。。=。=

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MAX 110
using namespace std;
int V,n,spe[MAX],get[MAX],sum,opt[10100];
void begin()
{
	freopen("medic.in","r",stdin);
	freopen("medic.out","w",stdout);
}
int work()
{
	cin>>V>>n;
	for (int i = 1; i <= n; i++)
	{
		cin>>spe[i]>>get[i];
		sum += spe[i];
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = V; j >= spe[i]; j--)
		{
			opt[j] = max(opt[j-spe[i]]+get[i],opt[j]);
		}
	}
	printf("%d",opt[V]);
	return 0;
}
void end()
{
	fclose(stdin);
	fclose(stdout);
}
int main()
{
//	begin();
	work();
//	end();
	return 0;
} 

二维dp：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MAX 110
using namespace std;
int V,n,spe[MAX],get[MAX],sum,opt[10100][MAX];
void begin()
{
	freopen("happy.in","r",stdin);
	freopen("happy.out","w",stdout);
}
int work()
{
	cin>>V>>n;
	for (int i = 1; i <= n; i++)
	{
		cin>>spe[i]>>get[i];
		get[i] *= spe[i];
		sum += spe[i];
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = V; j >= spe[i]; j--)
		{
			opt[j][i] = max(opt[j-spe[i]][i-1]+get[i],opt[j][i-1]);
		}
		for (int j = max(spe[i],V); j >= 1; j--)
		{
			opt[j][i]=opt[j][i-1];
		}
	}
	printf("%d",opt[V]);
	return 0;
}
void end()
{
	fclose(stdin);
	fclose(stdout);
}
int main()
{
//	begin();
	work();
//	end();
	return 0;
}