zoj 1013 Great Equipment

응, DP문제. 나는 예전에 dp가 양방향 복잡도의 해결 방안이라고 생각했는데 이 문제를 보고 깨달았어. 사실 복잡도를 낮출 수만 있다면 돼.이 문제는 가방 문제입니다. 두 가지 제한 조건이 있습니다. weight와size입니다. 그리고 여러 개의 가방이 있습니다.마지막으로 이 장비들은 몸에 맞게 평가절상될 수 있다.음...우리는 dp로 가방 하나를 해결하는 w,s는 매우 간단하지만, 여기는 안 된다. 왜냐하면 가방이 매우 많기 때문이다.우리의 이동 방정식은 n-1개와 n번째 가방 사이를 바꾸는 것이다. 이것은 앞에 n-1개의 가방이 모두 가득 찼을 때의 모든 가능한 상황을 알고 n번째 가방의 상황을 계산하는 것이다.
전이 공식은 f(n,i+x,j+y)= f(n-1,i,j)+k(n,x,y)이다.그 중에서 i, j는 n-1개의 가방에 모두 몇 개의 helm와 armor를 넣었는지, 그리고 x, y는 n개의 가방에 몇 개의 helm와 armor를 넣었는지, f 함수의 반환 결과는 몇 개의 boot이 있는지, k 함수는 n개의 가방에 x개의 helm와 y개의 armor가 있다면 몇 개의 boot를 넣을 수 있는지를 나타낸다.
음, 마지막으로 코드를 붙이기:

#include<cstring>
#include<iostream>
using namespace std;

const int MAX_CAP = 501;
const int MAX_CAR = 101;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt+", stdout);
#endif

	int carNo;
	int m[2][MAX_CAP][MAX_CAP];
	int wn[MAX_CAR], ws[MAX_CAR];
	int helm[3], armor[3], boot[3];
	int c1, c2, c3, d4;
	int index = 1;
	while(cin >> carNo)
	{
		if(!carNo)
		{
			break;
		}
		cin >> helm[0] >> helm[1] >> helm[2];
		cin >> armor[0] >> armor[1] >> armor[2];
		cin >> boot[0] >> boot[1] >> boot[2];
		cin >> c1 >> c2 >> c3 >> d4;
		
		for(int i=0;i<carNo;i++)
		{
			cin >> wn[i] >> ws[i];
		}

		int maxHelm = 0, maxArmor = 0;
		int prev = 0, now =1;
		memset(m, 0, sizeof(m));
		for(int loop =0;loop<carNo;loop++)
		{
			memset(m[now], -1, sizeof(m[now]));
			int hemlx = min(wn[loop]/helm[0], ws[loop]/helm[1]);
			for(int i=0; i<=hemlx;i++)
			{
				int armorx = min( (wn[loop]-helm[0]*i)/armor[0], (ws[loop] - helm[1]*i)/armor[1]);
				for(int j=0;j<=armorx;j++)
				{
					int bootx = min( (wn[loop] - helm[0]*i - armor[0]*j)/boot[0], (ws[loop]-helm[1]*i-armor[1]*j)/boot[1]);
					for(int a=0;a<=maxHelm;a++)
					{
						for(int b=0;b<=maxArmor;b++)
						{
							if(m[prev][a][b] != -1)
							{
								m[now][a+i][b+j] = max(m[now][a+i][b+j], m[prev][a][b] + bootx);
							}
						}
					}
				}
			}
			maxHelm += hemlx;
			maxArmor += min(wn[loop]/armor[0], ws[loop]/armor[1]);
			swap(prev, now);
		}

		int ans = 0;
		for(int i=0;i<=maxHelm;i++)
		{
			for(int j=0;j<=maxArmor;j++)
			{
				if(m[prev][i][j] < 0)
				{
					continue;
				}
				int sets = min(min(i/c1, j/c2), m[prev][i][j]/c3);
				ans = max(ans, sets*d4 + helm[2]*(i-sets*c1) + armor[2]*(j-sets*c2) + boot[2]*(m[prev][i][j] - sets*c3));
			}
		}

		if(index >1)
		{
			cout << endl;
		}
		cout << "Case " << index++ << ": "<< ans << endl;
	}
}