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

[rs.fran]

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!

 

[atlos]

se o que voce quer dizer com programação dinamica seja memória dinamica,não

aqui tem um bom tutorial explicando sobre alocação dinamica de memória em C

http://www.ime.usp.br/~pf/algoritmos/aulas/aloca.html

bons estudos

[Ricardo Pereira_738665]

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;
        }

[Leotanis Leite Moraes]

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.

[Ansi C]

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;