TEMA
PROBLEM 1288 - URI Fórum 1.0
Este tema fue resuelto y no puede recibir nuevas respuestas.
-
crbonilha respondido on ene 13 2014
O fato de você escolher as balas conformem elas ainda caibam, e segundo a sua ordenação, é uma escolha gulosa. Ou seja, parece uma boa escolha agora, mas nem sempre é a melhor escolha olhando-se como um todo.
Esse caso de teste faz seu algoritmo falhar:
1 4 10 21 4 10 4 10 4 10 30 12
Ve, o fato de escolher a primeira bala que pesa 21, impede que você possa escolher as outras, enquanto que se você ignorasse a primeira bala e escolhesse as três outras, seu poder seria maior.
Um dos algoritmos recomendados para lidar com esse tipo de problema é o Algoritmo da Mochila. Pesquise algo a respeito.
-
a11yson respondido 7 years ago
Realmente, o erro era esse mesmo da matriz só caber 50, mas não percebi antes e também não entendi por que os testes com capacidade 100 funcionavam com a matriz em 50. o.O
-
tiwizard respondido 7 years ago
Nao deveria dar certo =D... sua matriz não tem tamanho suficiente para capacidades > 50
-
a11yson respondido 7 years ago
Tentei com vários testes, com capacidade 100, 99... todos bateram com o Toolkit.
Nem aumentando as variáveis (já que o problema não especifica o tamanho) passou. 20% WA ainda.
-
tiwizard respondido 7 years ago
acho que seu código falha nos casos com capacidade alta (teste com capacidade 100)
-
a11yson respondido 7 years ago
20% de WA neste código. Alguém sabe onde está o erro?
#include <iostream> #include <cstdio> #include <memory.h> #define FOR(a) for(int i = 0; i < a; i++) #define max(a, b) a>b? a:b using namespace std; int N, resistencia, capacidade; int poder[50], peso[50]; int tab[50][51]; int dp(int id, int cabe) { if(tab[id][cabe] != -1) return tab[id][cabe]; if(id >= N || cabe <= 0) return tab[id][cabe] = 0; int naocoloca = dp(id+1, cabe); if(peso[id] <= cabe) { int coloca = poder[id] + dp(id+1, cabe - peso[id]); return tab[id][cabe] = max(coloca, naocoloca); } return tab[id][cabe] = naocoloca; } int main() { int casos; int res; scanf("%d", &casos); while(casos--) { memset(tab, -1, sizeof(int) * 50 * 51); scanf("%d", &N); FOR(N) scanf("%d %d", &poder[i], &peso[i]); scanf("%d %d", &capacidade, &resistencia); res = dp(0, capacidade); if(res >= resistencia) printf("Missao completada com sucesso\n"); else printf("Falha na missao\n"); } return 0; }
Obrigado.
-
js.100 respondido 8 years ago
Sim, é isso mesmo.
Posta o seu código. Fica mais fácil de encontrar um caso de teste que faz sua solução falhar.
Nesse meio tempo, assista esses vídeos sobre "0/1 Knapsack Problem": https://www.youtube.com/watch?v=EH6h7WA7sDw https://www.youtube.com/watch?v=8LusJS5-AGo
Os vídeos me ajudaram bastante a entender e encontrar onde eu estava errando. Uma imagem vale mais que mil palavras :)
-
aaabotaleb respondido 8 years ago
Quando utilizando o Algoritmo da Mochila, o último valor da matriz (o mais a direita no canto inferior) não é o resultado desejado? Fiz dessa maneira, apenas pegando-o na tabela, e recebo WA(20%). Alguém pode me ajudar com alguns casos de teste ou alguma indicação de falha na minha lógica?
Obrigado!
-
calban respondido 9 years ago
#include <iostream> #include <string> #include <cstring> #include <cctype> #include <stdio.h> #include <stdlib.h> #include <sstream> using namespace std; int main() { int n=0; cin >> n; if(n==0) cout << "Falha na missao" << endl; string teste; while(n>0) { bool w=false; register int x,y,k=0,p,r; cin >> teste; istringstream buffer(teste); buffer >> p; int aux=0,total=0; int vecx[p],vecy[p],melhor=0,my=0,totaly=0,g=0,h=0,indi=0; int testeu[p]; for(int i=0; i<p; i++) { cin >> x >> y; vecx[i]=x; vecy[i]=y; testeu[i]=0; } cin >> k; cin >> r; for(g=0; g<p; g++) { for(int s=1; s<p; s++) { melhor = vecx[s-1]/vecy[s-1]; for(h=0; h<p; h++) { if(vecx[h]/vecy[h]>=melhor && vecy[h]<=k && testeu[h]==0) { indi = h; w=true; } } } if(w==true) { testeu[indi]=1; if(vecy[indi]+totaly<=k) { total+=vecx[indi]; totaly+=vecy[indi]; // cout << " usado: " << vecx[indi]<<endl; } } w=false; melhor=0; my=0; } if(total>=r) { cout << "Missao completada com sucesso" << endl; } else { cout << "Falha na missao" <<endl; } n--; } }
Estou faz uma semana tentando e sempre recebo Wrong answer (20%), fiz muitos testes, sempre funciona! O toolkit não esta mais disponível e isso dificulta ainda mais para mim encontrar o erro!
-
jeanmarcosdarosa respondido on ene 13 2014
Opa, entendi, não estava muito familiarizado com PD, li alguns tópicos e entendi o problema, obrigado pela dica, já consegui resolver
-
jeanmarcosdarosa respondido on ene 12 2014
Olá, alguém sabe me dizer qual foi meu erro no código? Estou levando WA 10% não consegui imaginar um caso de teste que reproduza o problema, se tiverem mais casos de teste também ajuda :D
#include <cstdio> #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef struct{ int p; int b; } obj; bool compare(const obj &a, const obj &b){ if(a.b==0&&b.b==0) return (b.p<a.p); if(b.b==0) return true; if(a.b==0) return false; if((double)(b.p/b.b)<(double)(a.p/a.b)){ return true; } return false; } int main(){ int casos, n, k, r; vector<obj>::iterator it; scanf("%d", &casos); while(casos--){ scanf("%d", &n); vector<obj> bag(n); for(int i=0;i<n;i++){ scanf("%d", &bag[i].p); scanf("%d", &bag[i].b); } scanf("%d", &k); scanf("%d", &r); sort(bag.begin(), bag.end(), compare); it = bag.begin(); int power = 0; while(k&&it!=bag.end()){ if(it->b<=k){ k-=it->b; power+=it->p; } ++it; } (power>=r)?printf("Missao completada com sucesso\n"): printf("Falha na missao\n"); } return 0; }
-
jbez10 respondido on jun 10 2013
Muito obrigado pelo feedback! Já corrigimos a descrição do problema.
-
marcelovca90 respondido on jun 8 2013
Sobre a saída, é dito: "Se o dano total das cargas carregadas for maior que a resistência do castelo então deverá ser impressa a mensagem “Missao completada com sucesso”, caso contrário, deverá ser impressa a mensagem “Falha na missao”."
Porém, na terceira entrada do exemplo, o maior dano causado pelo canhão é 1020, a resistência é 1020, e a saída é "Missao completada com sucesso". Então, creio que no enunciado deveria estar escrito "maior ou igual".