• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Warrior

[5] Phidias - Nível elevado

4 mensagens neste tópico

Título:

Phidias (adaptado de IOI 04 - Day 1 - Phidias)

Objectivo:

Phidias, o conhecido escultor Grego, prepara mais uma das suas obras.

Para isso, ele precisa de painéis rectangulares de mármore de tamanho C1 x H1, C2xH2, .., Cn x Hn.

Recentemente, Phidias recebeu uma grande e rectangular peça de mármore, que vai cortar de modo a formar as peças mais pequenas que necessita.

Qualquer pedaço de mármore (a peça inicial ou qualquer placa obtida após o primeiro corte) pode ser cortado ou na horizontal ou na vertical em duas outras placas com largura e altura inteiras. Esta é a única forma de cortar peças, e as peças não podem ser coladas.

Como a mármore tem um padrão, as placas não podem ser rodadas: se ele corta uma placa de tamanho A x B, não pode ser usada como uma placa de tamanho B x A (excepto se A = B, obviamente)

Ele pode fazer 0 ou mais placas de cada um dos tamanhos pretendidos. (é um monumento bastante grande)

Um pedaço de mármore é desperdiçado se, no final de todos os cortes, não possui as dimensões necessárias.

Phidias questiona-se sobre qual a melhor maneira de cortar a peça, de modo a minimizar a área desperdiçada.

Como um exemplo, assumam que na figura que se segue a largura inicial era 21 e a altura 11. Os tamanhos das peças necessárias são: 10x4, 6x2, 7x5, 15x10.

A área mínima desperdiçada é 10, e a figura mostra uma possível sequência de cortes com essa área desperdiçada.

phidiasmw2.jpg

O teu objectivo é fazer um programa que dada uma peça original e as dimensões das placas necessárias, calcule a área mínima desperdiçada.

Explicação de Input

A primeira linha do input contem dois inteiros: L, a largura da placa original, e H, a altura da placa.

A segunda linha contem um inteiro, N, o número de diferentes tamanhos possíveis.

As seguintes N linhas contém os tamanhos das placas. Cada linha com dois inteiros: Li e Hi, respectivamente a largura e a altura da placa correspondente.

Explicação de Output

Um único inteiro, a área mínima desperdiçada.

Exemplo de input/output

Input:

21 11

4

10 4

6 2

7 5

15 10

Output:

10

Material de apoio:

Não aplicável.

Restrições:

O programa deve responder com sucesso a um input que siga estes limites:

1 <= L,H <= 600

1 <= N <= 200

1 <= Li <= L

1 <= Hi <= H


Discussão do problema em:

http://www.portugal-a-programar.pt/index.php?showtopic=16725

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Deixo aqui a minha solução com Programação Dinâmica.

Não é certamente a mais simples de compreender, mas dá para ver que a solução, afinal, não é complicada de escrever.

Deixo a solução com Memoization para ti mogers.

#include <stdio.h>
#include <string.h>

#define MAX 605

int m[MAX][MAX];

int l,c;

void ler() {
 int n,a,b;
 memset(m,0xFF,sizeof(m));
 scanf("%d %d",&l,&c);
 scanf("%d",&n);
 for (int i=0;i<n;i++) {
   scanf("%d %d",&a,&b);
   m[a][b]=0;
 }
}

void solve() {
 int min;
 for (int i=1;i<=l;i++) {
   for (int j=1;j<=c;j++) {
     if (m[i][j]==0)
continue;
     min=i*j;
     for (int k=1;k<i;k++)
if (min>m[k][j]+m[i-k][j])
  min=m[k][j]+m[i-k][j];
     for (int k=1;k<j;k++)
if (min>m[i][k]+m[i][j-k])
  min=m[i][k]+m[i][j-k];
     m[i][j]=min;
   }
 }
}

int main() {
 ler();
 solve();
 printf("%d\n",m[l][c]);
 return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Deixo a solução com Memoization para ti mogers.

Aqui está ela :) 

Primeiro fiz com memoization (ir calculando e guardar resultados numa tabela), mas depois alterei para a forma como fizeste.

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 601
using namespace std;

int dp[MAX][MAX];	// desperdicio com uma peca LxH

int calcula( int L , int H ) {
int & r = dp[L][H] , i ;
if ( r >= 0 )		return r;     // o desperdicio com estas dimensoes ja foi calculado, retorna o valor da tabela
if ( L == 0 || H == 0 )	return r = 0; // tamanho 0 e' o mesmo que nada

r = L * H;	// tudo desperdicado

for (i = 1 ; i < L ; i++)	// corte horizontal
	r = min( r , calcula( i , H ) + calcula( L-i , H ) );
for (i = 1 ; i < H ; i++)	// corte vertical
	r = min( r , calcula( L , i ) + calcula( L , H-i ) );
return r ;
}
int main()
{
memset( dp , -1 , sizeof(dp) );
int L , H , N , i , j;
cin >> L >> H >> N;
while (N--) {
	cin >> i >> j;
	dp[i][j] = 0;	// pecas com dimensoes necessitadas nao provocam desperdicio
}
cout << calcula( L , H ) << endl;
return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estava-me a apetecer resolver um problema deste tipo (DP). E então decidi resolver este. É escusado dizer que o vosso código foi uma fantástica fonte de inspiração :)

Em Haskell obviamente ;)

import Control.Arrow
import Data.Array

main = do
   lh <- getLine >>= return . toPair . map read . words
   n <- readLn
   pecas <- getContents >>= return . map (toPair . map read) . map words . take n . lines
   print $ solveIt lh pecas

toPair [x,y] = (x,y)

solveIt s@(l,h) ps = arr!s -- Saca desperdicio do tamanho original da posição do array
   where
   arr = array ((0,0),s) $ [ (id &&& f) (i,j) | i <- [0..l], j <- [0..h]] -- Constroi array com os desperdicios (lazy)
                         ++ zip ps (repeat 0) -- Coloca desperdicios das peças a 0
   f (0,_) = 0  -- Não existe
   f (_,0) = 0  -- Não existe
   f (i,j) = minimum $ i*j  -- Desperdicio máximo
                     :  (map (\x -> arr!(x,j) + arr!(i-x,j)) [1..i-1]) -- Corta pelas linhas
                     ++ (map (\x -> arr!(i,x) + arr!(i,j-x)) [1..j-1]) -- Corta pelas colunas

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora