C/Visual C - Problema de asignación en C/C++

   
Vista:

Problema de asignación en C/C++

Publicado por Dudu (1 intervención) el 17/06/2016 13:50:38
Buenas, tengo que hacer un ejercicio de clase que consiste en hacer programa en C o C++ que se ejecute lo más rapido posible alcanzando alguna o ninguna solucion, y no se muy bien como enfocarlo. Es el siguiente:

Mecánicos y Averías

Contexto

Estás trabajando de informático en una empresa que se dedica a reparar maquinaria pesada. Cada mecánico puede reparar ciertos tipos de avería.
La reparación de una avería requiere de la asignación de un mecánico, y cada mecánico puede estar asignado cada día a un máximo de una avería.
La empresa te pide que diseñes un programa que permita optimizar la asignación diaria de mecánicos a averías, de modo que se consiga reparar el máximo posible de averías cada día.

El Problema

Tenemos M mecánicos y A averías por reparar. Una tabla bidimensional C, de elementos booleanos c(i,j), indica que el mecánico i tiene capacidad para reparar la avería j.
Se debe realizar una asignación de mecánicos a averías que maximice el número de averías reparadas en el día, teniendo en cuenta que cada mecánico puede ser asignado a una única avería.
Se admitirá cierto margen en la solución respecto del óptimo: cualquier solución que alcance el 60% del óptimo será considerada válida.

Entrada

La primera línea de la entrada contiene un entero, P, que indica el número de casos de prueba.
Cada caso de prueba contiene 1+M líneas:
la primera línea tiene dos enteros, M y A, que indican el número de mecánicos y de averías, respectivamente;
las siguientes M líneas contienen A enteros cada una, separados por espacios en blanco, correspondiendo el entero j-ésimo de la línea i a la capacidad
del mecánico i para reparar la avería j, es decir, el elemento c(i,j) de la tabla C. Un 1 indica que el mecánico i puede arreglar la avería j, y un 0 indica que no.

Salida

La primera línea de la salida contiene un entero, P, que indica el número de casos de prueba (es decir, el mismo que el de entrada).
Para cada caso, la salida deberá tener dos líneas:
la primera línea es el número total de averías reparadas.
la segunda línea indica qué mecánico se asignó a cada avería. Contendrá A números enteros, separados por espacios en blanco, donde
el entero j-ésimo indica el mecánico asignado a la avería j; para las averías no reparadas se utilizará el número 0.

Ejemplo de Entrada

3
2 3
0 1 0
0 0 0
4 3
1 0 1
1 1 0
0 0 0
1 1 1
2 3
0 0 1
1 0 1

Ejemplo de Salida

3
1
0 1 0
3
1 2 4
2
2 0 1

Tengo el siguiente pseudocodigo general de asignacion de trabajadores dentro de sus plazos pero no se muy bien como programarlo y seguramente le falten cosas (añadir averias,etc..):

operacion Trabajos (d:array[1..n] de entero; var s:array[1..n] de 0..n)
d[0]:=0
s[0]:=0
//actuan de centinelas
k:=1
s[1]:=1
//incluye el primer trabajo
para i:=2...n hacer
r:=k
//k indica la cantidad de trabajos incluidos
//y r tendrá la posición donde se ejecuta el nuevo trabajo
mientras d[s[r]]>d Y d[s[r]] !=r hacer
r:= r-1
finmientras
//se busca mantener la solución ordenada crecientemente por [i]d

//se consigue moviendo a la derecha los trabajos siempre que queden dentro de su plazo
si d[s[r]] =< d[i] Y d[i]>r entonces
//si estan en orden y se puede incluir el trabajo i
para l:=k,..,r+1 hacer
s[l+1]:=s[l]
finpara
s[r+1]:=i
//ha puesto i en su lugar de ejecución
k:= k+1
finsi
finpara

Si alguien sabe de C y puede ayudarme se lo agradeceria muchisimo, me urge.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder