0809-saco-do-papai-noel

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 809 idBeecrowd: 1767 name: Saco do Papai Noel origin: beecrowd topics: - o-problema-da-mochila - programacao-dinamica slug: saco-do-papai-noel authorSlugEditorial: alessio authorSlugProblem: neilor-tonin description: Otimização clássica do '0/1 Knapsack Problem'. O algoritmo demanda maximizar o somatório de valores (blocos independentes) limitando-se a uma capacidade paramétrica restrita W, aferindo ineficácia de relaxamentos gulosos O(N log N). editorial: O problema é resolvido utilizando o paradigma de Programação Dinâmica, especificamente o algoritmo da Mochila 0/1 (0/1 Knapsack). Com uma capacidade fixa de 50 kg e no máximo 100 pacotes, construímos uma tabela DP para armazenar a maior quantidade de brinquedos para cada peso possível. Ao final, recuperamos o peso total utilizado e a quantidade de pacotes restantes através do rastreamento dos itens selecionados na tabela. successmsg: Matriz O(N*W) de transição estabelecida. O rastreamento (backtracking tabular) decodificou correta dependência de sub-estado, blindando as instâncias via DP Tabulation e Memoization O(1). difficultyLevelId: C timeComplexity: O(N) spaceComplexity: O(N) timeLimitSegs: 1 memoryLimitMb: 128 defaultStatement: a_pt_saco-do-papai-noel.md skills: - complexity-analysis - dp-solution-reconstruction - dp-states-transitions - knapsack-01 statements: - id: a-saco-do-papai-noel default: true testScenarioLevel: A thematicSkills: - points: 1 skill: delivery-postal testScenarios: - id: d-sample name: Exemplos do Enunciado description: Casos de teste básicos fornecidos no material original. helpTip: I/O Sanity Check e Reconstrução Básica. A aferição provê caso amigáveis para verificar não apenas o Score Máximo (DP) mas também formatar as quebras de linha dos itens complementares descartados. level: D testType: TDD skills: - points: 1 skill: knapsack-01 - id: a-performance-load name: Teste de Carga e Performance description: Casos com N=100 para validar se a solução usa DP em vez de recursão simples. helpTip: Saturação O(2^N). A densidade máxima inviabiliza ramificações nativas de busca Top-Down DFS (Time Limit Exceeded). Force incondicionalmente alocação da DP tabular ou Memoization robusto O(N*W). level: A testType: PERFORMANCE skills: - points: 2 skill: complexity-analysis - points: 1 skill: dp-states-transitions - id: b-edge-cases name: Casos de Borda description: Pesos maiores que o limite, lista vazia ou itens que não cabem. helpTip: Empty States Estritos. Verifique matrizes inicializadas em Zero onde todos os pesos singulares Wt_i excedem prematuramente o Limit W, não selecionando bloco algum. Mantenha os arrays livres de acessos Index Out Of Bounds. level: B testType: TDD skills: - points: 1 skill: dp-states-transitions - points: 1 skill: knapsack-01 - id: c-logic-complex name: Lógica e Reconstrução description: Casos que quebram algoritmos gulosos e exigem reconstrução precisa da solução. helpTip: Reconstrução Restrita pós-Matrix (DP Traceback). Operações que derivam 'Quantos pacotes restaram' baseiam-se em subtrair os blocos processados no Delta de Matriz[i][w] versus Matriz[i-1][w]. level: C testType: TDD skills: - points: 2 skill: dp-solution-reconstruction - points: 1 skill: knapsack-01 solutions: - id: a-optimal name: Solução Ótima (Programação Dinâmica) description: Implementação utilizando o algoritmo da mochila 0/1 com complexidade O(N*W), garantindo o máximo de brinquedos dentro do limite de peso. level: A implementations: - filenames: - solution.c language: c paradigm: Imperative - filenames: - Solution.cpp language: cpp paradigm: Imperative - filenames: - Main.java language: java paradigm: Imperative main: Main - filenames: - solution.py language: py paradigm: Imperative - id: b-suboptimal name: Solução Sub-ótima (Busca Exaustiva) description: Implementação recursiva sem memorização com complexidade O(2^N). É correta logicamente mas deve falhar por tempo (TLE) para entradas maiores. level: B implementations: - filenames: - solution.py language: py paradigm: Functional