TÓPICO

PROBLEM 1288 - URI Fórum 1.0

beecrowd perguntou on fev. 8 2013

URI Online Judge Fórum 1.0

MOD

Este tópico foi resolvido e não pode receber novas respostas.

  • crbonilha respondido on jan. 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

    Agora quero saber uma forma para otimizá-lo.

    Alguém pode me ajudar?

  • 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 jan. 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 jan. 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".