Grátis: A abordagem de força bruta para resolver o problema de corte de barras envolve gerar todas as combinações possíveis de cortes e comparar os valores... – Questões Respondidas

Lógica de Programação

Outros

A abordagem de força bruta para resolver o problema de corte de barras envolve gerar todas as combinações possíveis de cortes e comparar os valores de venda. No entanto, essa abordagem é ineficiente devido ao tempo de execução exponencial, uma vez que existem 2(N−1)2 combinações possíveis de cortes para uma barra de comprimento N. Em vez disso, podemos usar uma abordagem recursiva, aproveitando o fato de que a solução ótima para um problema de comprimento N é uma composição das soluções ótimas de subproblemas de tamanhos menores. Em cada nível de recursão, executa-se apenas um único corte e considera-se uma solução ótima para a barra restante.

Considere uma barra de comprimento 4 e a seguinte tabela de preços para cada comprimento:

Comprimento (i) Preço (p[i])

1 2

2 5

3 7

4 8
Agora, utilize uma abordagem recursiva para computar a receita máxima obtida ao cortar a barra e selecione a alternativa correspondente.
A. 8
B. 9
C. 11
D. 12
E. 10

Testando o Conhecimento

há 2 semanas

Testando o Conhecimento

há 2 semanas

COM540-2026S2B1-T001S6 - Atividade Avaliativa_ Revisão da tentativa _ UNIVESP

UNIVESP

Respostas

Ed

há 2 semanas

Vamos analisar passo a passo para encontrar a receita máxima ao cortar a barra de comprimento 4, usando a tabela de preços: Comprimento (i) | Preço (p[i]) 1 | 2 2 | 5 3 | 7 4 | 8 A ideia é calcular a receita máxima para cada comprimento menor ou igual a 4, considerando todas as possíveis divisões. Definimos R(n) como a receita máxima para uma barra de comprimento n. - R(0) = 0 (barra de comprimento zero não gera receita) Calculamos R(1): - Cortar em 1: preço p[1] = 2 Logo, R(1) = 2 Calculamos R(2): - Cortar em 1 + R(1) = p[1] + R(1) = 2 + 2 = 4 - Cortar em 2: p[2] = 5 Máximo é 5 Logo, R(2) = 5 Calculamos R(3): - Cortar em 1 + R(2) = 2 + 5 = 7 - Cortar em 2 + R(1) = 5 + 2 = 7 - Cortar em 3: p[3] = 7 Máximo é 7 Logo, R(3) = 7 Calculamos R(4): - Cortar em 1 + R(3) = 2 + 7 = 9 - Cortar em 2 + R(2) = 5 + 5 = 10 - Cortar em 3 + R(1) = 7 + 2 = 9 - Cortar em 4: p[4] = 8 Máximo é 10 Portanto, a receita máxima para a barra de comprimento 4 é 10. Resposta correta: E. 10

Essa resposta te ajudou?

0

0

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

COM540-2026S2B1-T001S6 - Atividade Avaliativa_ Revisão da tentativa _ UNIVESP

UNIVESP

Mais perguntas desse material

A programação dinâmica é uma técnica utilizada para otimizar a resolução de problemas complexos, dividindo-os em subproblemas menores e resolvendo-os de forma eficiente. Existem duas abordagens principais para implementar a programação dinâmica: Top-Down e Bottom-Up. Ambas visam melhorar a eficiência do algoritmo ao gerenciar e reutilizar os resultados dos subproblemas de maneiras diferentes.
Com base na contextualização apresentada, assinale a alternativa que define as abordagens Top-Down e Bottom-Up na programação dinâmica.
A. A abordagem Top-Down utiliza uma estrutura recursiva, salva os resultados de subproblemas resolvidos, e evita cálculos repetidos, enquanto a abordagem Bottom-Up é iterativa, resolve subproblemas do menor para o maior, e constrói a solução final.
B. A abordagem Top-Down calcula os subproblemas do menor para o maior sem salvar resultados intermediários, enquanto a abordagem Bottom-Up evita cálculos repetidos, usa memorização, e armazena todos os resultados em uma tabela.
C. A abordagem Top-Down resolve subproblemas de forma paralela, armazena resultados intermediários para evitar redundâncias, enquanto a abordagem Bottom-Up utiliza uma estrutura recursiva, resolve do maior para o menor, e depende de cálculos repetidos.
D. A abordagem Top-Down é iterativa, resolve subproblemas do maior para o menor, sem utilizar recursão, enquanto a abordagem Bottom-Up resolve subproblemas de forma sequencial, armazena resultados de subproblemas em uma tabela e constrói a solução final.
E. A abordagem Top-Down armazena resultados intermediários para evitar cálculos redundantes e utiliza uma estrutura recursiva, enquanto a abordagem Bottom-Up trabalha de forma iterativa, resolvendo subproblemas do menor para o maior, e evita cálculos repetidos.

A sequência de Fibonacci é um exemplo clássico para ilustrar a programação dinâmica. Esta sequência tem aplicações em diversas áreas do cotidiano, como na biologia, onde é observada no padrão de crescimento de certas plantas e na disposição das folhas; na música, onde a sequência pode ser encontrada na estrutura de certas composições; e na ciência da computação, onde é utilizada em algoritmos e estruturas de dados. A definição formal da sequência de Fibonacci é representada da seguinte forma: F (n )=1 se n=1 ou n=2, e F (n )=F (n−1)+F (n−2) para n>2 .
Com base na contextualização apresentada, assinale a alternativa que apresenta o 8º número da sequência de Fibonacci.
A. 89
B. 34
C. 13
D. 55
E. 21

A programação dinâmica permite calcular a solução ótima de forma eficiente, evitando a necessidade de explorar todas as combinações possíveis de itens, o que seria inviável para grandes conjuntos de dados.

Considere uma mochila com capacidade de 10 kg e os seguintes itens, cada um com seu respectivo peso e valor:

Item Peso (kg) Valor ($)

1 2 3

2 3 4

3 4 5

4 5 8
Agora, aplique uma abordagem de programação dinâmica para determinar o valor máximo que pode ser obtido ao colocar itens na mochila, assinale a alternativa que corresponde a esse valor:
A. 12
B. 8
C. 9
D. 11
E. 10

A multiplicação de matrizes não é comutativa, mas é associativa, permitindo diferentes associações na multiplicação de uma cadeia de matrizes. A forma como associamos as matrizes afeta diretamente o custo computacional. Por exemplo, ao multiplicar quatro matrizes A,B,C,D, podemos realizar a multiplicação de várias maneiras, como (A×B)×(C×D) ou (A×(B×C))×D.

Sobre a programação dinâmica aplicada ao problema da multiplicação de cadeias de matrizes, analise as afirmativas a seguir:
Está correto o que se afirma em:
I. A propriedade associativa da multiplicação de matrizes garante que todas as ordens possíveis de multiplicação resultam no mesmo custo computacional.
II. A programação dinâmica é utilizada para determinar a ordem ótima de multiplicação de matrizes que minimiza o custo computacional.
III. O custo computacional de multiplicar três matrizes A,B,C com dimensões 10 × 100, 100 × 5 100 e 5 × 50 é minimizado pela associação (A×B)×C.
IV. O algoritmo de programação dinâmica para multiplicação de matrizes utiliza uma tabela de custos para armazenar os resultados das subcadeias de multiplicação.
A. I, II e IV, apenas.
B. II e IV, apenas.
C. II, III e IV, apenas.
D. I e II, apenas.
E. I e III, apenas.

O custo computacional da multiplicação de cadeias de matrizes pode variar significativamente dependendo da ordem das multiplicações. Por exemplo, ao multiplicar quatro matrizes, diferentes associações podem resultar em diferentes números de multiplicações. Em um caso, multiplicar B por C, depois o resultado por D, e finalmente por A resulta em 120.200 multiplicações. Em outro caso, multiplicar A por B, depois C por D, e então os resultados, totalizam apenas 7.000 multiplicações. Essa variação ilustra a importância de escolher a ordem de multiplicação que minimize o custo.

Esse conceito pode ser comparado com a eficiência na organização de tarefas diárias. Por exemplo, se você tem várias tarefas para realizar, a ordem em que você as executa pode influenciar significativamente o tempo total necessário para completá-las. Otimizar a sequência das tarefas pode resultar em economia de tempo e esforço, similar ao que acontece na multiplicação de matrizes.

Com base na contextualização apresentada, observe as dimensões das matrizes:

A é uma matriz 10 × 30.

B é uma matriz 30 × 5.

C é uma matriz 5 × 60.

D é uma matriz 60 × 2.
Agora, assinale a alternativa que apresenta o número de multiplicações necessárias ao multiplicar a sequência de matrizes A×(B×(C×D)), de acordo com as dimensões de matrizes inseridas anteriormente:
A. 3000
B. 1000
C. 2000
D. 1500
E. 3500

Utilizando um algoritmo top-down, são criados dois vetores: um vetor B para armazenar o lucro máximo para uma barra de tamanho K, e um vetor S para armazenar a posição onde o corte foi realizado. Inicializa-se o caso base com lucro zero para uma barra de comprimento zero e inicializa-se B com lucro valendo -1. Durante a chamada recursiva, verifica-se se B já foi resolvido. Se não, executa-se o procedimento, caso contrário, devolve-se o valor já resolvido.

Uma empresa deseja maximizar o lucro cortando barras de aço de diferentes comprimentos. Considere uma barra de comprimento 5 e a seguinte tabela de preços:

Comprimento (polegadas) Preço ($)

1 1

2 5

3 8

4 9

5 10
Agora, utilize a programação dinâmica e o algoritmo top-down, calcule a combinação de cortes que maximiza o lucro para uma barra de 5 polegadas e o valor do lucro máximo e assinale a alternativa que corresponde a esses valores.
A. Combinação: 2+2+1, Lucro máximo: R$12,00
B. Combinação: 1+1+3, Lucro máximo: R$12,00
C. Combinação: 1+4, Lucro máximo: R$10,00
D. Combinação: 5, Lucro máximo: R$10, 00
E. Combinação: 2+3, Lucro máximo: R$13,00

O problema de corte de hastes envolve determinar a melhor forma de cortar hastes de aço. Cada corte é gratuito, e o objetivo é encontrar a combinação de cortes que resulta na maior receita possível. Conhecendo o preço pi para hastes de i polegadas, a questão é decidir se é mais lucrativo cortar a haste ou vendê-la inteira.
Com base no conteúdo apresentado, assinale a alternativa que descreve como a programação dinâmica pode ser utilizada para resolver o problema de corte de hastes.
A. A programação dinâmica resolve o problema utilizando algoritmos de força bruta, recalculando as receitas para cada subproblema sempre que necessário.
B. A programação dinâmica determina a receita máxima através de uma busca exaustiva de combinações, sem considerar soluções anteriores.
C. A programação dinâmica resolve ao considerar todas as combinações possíveis de cortes e calcular a receita.
D. A programação dinâmica utiliza uma abordagem recursiva que armazena resultados de subproblemas resolvidos, evitando cálculos redundantes.
E. A programação dinâmica ignora as soluções ótimas de subproblemas e calcula a receita máxima sem armazenar valores intermediários.