Ir ao conteúdo
  • Cadastre-se
rs.fran

Dúvida em reconhecer programação dinâmica

Recommended Posts

Olá! Estou estudando programação dinâmica e encontrei um algoritmo do problema da mochila, porém não consegui reconhecer se ele é ou não implementado por programação dinâmica, poderiam me ajudar? Caso ele seja pd, poderiam me explicar por que?
 

#include <stdio.h>#include <stdlib.h>#include <string.h> struct {    double val, wgt, vol;    const char * name;} items[] = { // value in hundreds, volume in thousandths    {30, .3, 25,    "panacea"},    {18, .2, 15,    "ichor"},    {25, 2., 2,    "gold"},    {0,0,0,0}}; /* silly setup for silly task */int best_cnt[16] = {0}, cnt[16] = {0};double best_v = 0; void grab_em(int idx, double cap_v, double cap_w, double v){    double val;    int t = cap_w / items[idx].wgt;    cnt[idx] = cap_v / items[idx].vol;     if (cnt[idx] > t) cnt[idx] = t;     while (cnt[idx] >= 0) {        val = v + cnt[idx] * items[idx].val;        if (!items[idx + 1].name) {            if (val > best_v) {                best_v = val;                memcpy(best_cnt, cnt, sizeof(int) * (1 + idx));            }            return;        }        grab_em(idx + 1, cap_v - cnt[idx] * items[idx].vol,            cap_w - cnt[idx] * items[idx].wgt, val);        cnt[idx]--;    }} int main(void){    int i;     grab_em(0, 250, 25, 0);    printf("value: %g hundreds\n", best_v);    for (i = 0; items[i].name; i++)        printf("%d %s\n", best_cnt[i], items[i].name);     return 0;}

Obrigada!

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Não é programação dinamiica

 

namespace Prob_mochla
{
    class Program
    { /*Atributos da classe*/
        /*string: atributo que recebe os dados de saída de printOptmalParents()
        * para poder exibir o resultado da parentização. */
        public static string texto;
        /*m: atributo que recebe os valores das multiplicações feitas para o melhor custo*/
        private static int[,] m;
        /*s: atributo que recebe o valor das posições de melhor multiplicação*/
        private static int[,] s;
        /*linhas: recebe o valor total das linhas das matrizes.*/
        private static int linhas;
        /*colunas: recebe ovalor total das colunas das matrizes*/
        private static int colunas;
        private static Boolean inicioMatriz;


        public static int[,] MatrixChainOrder(int[] p)
        {
            int[,] retorno = new int[p.Length - 1, p.Length - 1];
            //try
            {
                int i = 0; //linhas
                int j = 0; //colunas
                int k = 0;
                int q = 0;
                int infinito = int.MaxValue;//Integer.MAX_VALUE; // tipo infinito positivo (para simular o infinito)
                int n = p.Length - 1;
                int[,] m = new int[n, n]; // ixj
                int[,] s = new int[n, n];
                for (i = 0; i < n; i++)
                {
                    m[i, i] = 0;
                }
                for (int l = 1; l < n; l++)
                {
                    for (i = 0; i < n - l; i++)
                    {
                        j = i + l;
                        m[i, j] = int.MaxValue;//infinito;
                        for (k = i; k < j; k++)
                        {
                            q = m[i, k] + m[k + 1, j] + p * p[k + 1] * p[j + 1];
                            if (q < m[i, j])
                            {
                                m[i, j] = q;
                                s[i, j] = k + 1;
                            }
                        }
                    }
                }
                retorno = s;
            } /*catch (Exception e) {
            System.out.println("Erro: " + e);
            e.printStackTrace();*/
            return retorno;
        }

        public String printOptmalParents(int[,] s, int i, int j)
        {
            if (i == j)
            {
                texto += "A" + (i + 1) + " ";
            }
            else
            {
                texto += " ( ";
                printOptmalParents(s, i, s[i, j] - 1);
                printOptmalParents(s, s[i, j], j);
                texto += " ) ";
            }
            return texto;
        }
        public static void inicializaRecursiveMatrixChain(int[] p)
        {
            int n = p.Length - 1;
            m = new int[n, n]; // ixj
            s = new int[n, n];
            inicioMatriz = true;
        }
        public static int recursiveMatrixChain(int[] p, int i, int j)
        {
            int retorno = 0;
            if (inicioMatriz)
            {
                if (i == j)
                {
                    retorno = 0;
                }
                else
                {
                    m[i, j] = int.MaxValue;//Integer.MAX_VALUE;
                    for (int k = i; k <= j - 1; k++)
                    {
                        int q = recursiveMatrixChain(p, i, k) + recursiveMatrixChain(p, k + 1, j) + p * p[k + 1] * p[j + 1];
                        if (q < m[i, j])
                        {
                            m[i, j] = q;
                            s[i, j] = k + 1;
                        }
                    }
                    retorno = m[i, j];
                }
            }
            return retorno;
        }

Compartilhar este post


Link para o post
Compartilhar em outros sites

Cara, ja resolvi este mesmo problema em outro tópico. Tambem nao entendi o termo programação dinâmica, mas este exercicio você resolve utilizando pilha de dados. você cria uma função para criar uma pilha de dados (pilha de dados= onde você só pode retirar dados do topo ou botar dado em cima do topo).

 

Depois você cria uma função bool para retornar positivo se a pilha esta cheia,

 

Cria ou função para armazenar dados na pilha, onde o dado sera armazenado na variavel+1 onde variavel é o valor do ponteiro que acusa o topo da pilha, depois acrescendo +1 para este ponteiro.

 

E cria uma função para retirar dados da pilha, onde vai retirar no endereço do topo, e depois fazer topo-1.

 

Lembrando sempre que para retirar dados ou incluir dados na pilha, veririfcar se o mesmo esta cheio ou nao.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Não é programação dinâmica;

A pode parecer preconceito, de quem está apenas aprendendo,

contudo ainda percebo um deficiência gravíssima nesta algoritmo dentro muitas coisa a recursão;

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×