Cazare

[•chera_lary]

Salut!

Problema : Problema Cazare

Nu stiu de ce nu merge! Depasesc si memoria si pic si teste! Daca nu gasiti problema pe codul meu, va rog sa imi lasati o idee de abordare, adica cum sa aplic metoda rucsacului ( in cazul in care nu am aplicat-o bine )!

Practic recurenta mea se bazeaza pe urmatoarea relatie:
sol[k][ b][f] = k daca sol[k-1][b-B[k]][f-F[k]] != 0 si sol[k-1][ b][f] daca este 0; In problema notatiile sunt altele, dar ideea este aceeasi!
Initial completez matricele sol[k][ b][f] = k, intr-un for.

Cod:

for(int i=1;i<=K;i++)
	{
		in>>clasa[i][0]>>clasa[i][1];
		for(int j=1;j<=i;j++)
			sol[i][clasa[j][0]][clasa[j][1]] = j;
	}

Cod:

#include <fstream>
#include <iostream>
#include <vector>
#include <memory>
#include <alloc.h>

#define bfMax 	1000
#define kMax 	101

#define fin 	"cazare.in"
#define fout 	"cazare.out"

using namespace std;

int B, F, K;
int clasa[kMax][2];

//bool sol[kMax][bfMax][bfMax];
//int  alege[kMax][bfMax][bfMax];
int ***sol;
//int ***alege;

void citeste()
{
	fstream in(fin, ios::in);
	in>>B>>F>>K;
	
	sol = (int***)malloc(sizeof(int**)*(K+1));
	//alege = (int***)malloc(sizeof(int**)*(K+1));
	for(int i=0;i<=K;i++)
	{
		sol[i] = (int**)malloc(sizeof(int*)*(B+1));
		//alege[i] = (int**)malloc(sizeof(int*)*(B+1));
		for(int j=0;j<=B;j++)
			sol[i][j] = (int*)malloc(sizeof(int)*(F+1)),
			//alege[i][j] = (int*)malloc(sizeof(int)*(F+1)),
			memset(sol[i][j], 0, sizeof(int)*(F+1));
			//memset(alege[i][j], 0, sizeof(int)*(F+1));
	}
	
	for(int i=1;i<=K;i++)
	{
		in>>clasa[i][0]>>clasa[i][1];
		for(int j=1;j<=i;j++)
			sol[i][clasa[j][0]][clasa[j][1]] = j;
	}
	in.close();
}

void solve()
{
	int w1, w2;
	
	for(int k=1;k<=K;k++)
	{
		for(int i=1;i<=B;i++)
			for(int j=1;j<=F;j++)
			{
				w1 = clasa[k][0];
				w2 = clasa[k][1];
				//sol[k][w1][w2] = k;
				//alege[k][w1][w2] = k;
				if(w1 <= i && w2 <= j)
				{
					if(sol[k-1][i-w1][j-w2] && !sol[k][i][j])
					{
						sol[k][i][j] = k;
						continue;
						//alege[k][i][j] = k;
					}
					else if(sol[k][i][j] == 0)
					{
						sol[k][i][j] = sol[k-1][i][j];
						continue;
						//alege[k][i][j] = alege[k-1][i][j];
					}
				}
				else if(sol[k][i][j] == 0)
				{
					sol[k][i][j] = sol[k-1][i][j];
					//alege[k][i][j] = alege[k-1][i][j];
				}
			}
			
		if(sol[k][B][F]>0)
		{
			K=k;
			break;
		}
	}
}

void tipar()
{
	int x=B, y=F, k=K, X;
	int object;
	
	vector<int> solution;
	
	while(sol[k][x][y])
	{
		object = sol[k][x][y];
		
		X = x;
 		solution.push_back(sol[k][x][y]);
 		x -= clasa[sol[k][x][y]][0];
		y -= clasa[sol[k][X][y]][1];
		k--;
		
		/*while(object == sol[k][x][y])
		{
			X = x;
			x -= clasa[sol[k][x][y]][0];
			y -= clasa[sol[k][X][y]][1];
			k--;
		}*/
	}
	
	fstream out(fout, ios::out);
	out<<solution.size()<<endl;
	for(int i=solution.size()-1;i>=0;i--) out<<solution[i]<<endl;
	
	/*for(int i=0;i<=K;i++)
	{
		out<<i<<":"<<endl;
		for(int j=0;j<=B;j++)
		{
			for(int k=0;k<=F;k++)
				out.width(2), out<<sol[i][j][k]<<" ";
			out<<endl;
		}
	}*/
	out.close();
}

void Drum(int k, int x, int y, ofstream &out)
{
	if(sol[k][x][y])
	{
		Drum(k-1, x-clasa[sol[k][x][y]][0], y-clasa[sol[k][x][y]][1], out);
		out<<sol[k][x][y]<<endl;
	}
}

int main(void)
{
	citeste();
	solve();
	//ofstream out(fout);
	//Drum(K, B, F, out);
	//out.close();
	tipar();
	
	/*for(int i=0;i<=K;i++)
	{
		for(int j=0;j<=B;j++)
			free(sol[i][j]);
			
		free(sol[i]);
	}
	
	free(sol);*/
	
	return 0;
}