knapsack/index.html at main · sortphy/knapsack · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
<!DOCTYPE html>
<html lang="pt-BR">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Problema da Mochila | Sortphy</title>
  <link rel="icon" href="./images/sortphy.png">
  <link rel="stylesheet" href="styles.css">

  <script defer src="script.js"></script>

</head>
<body>
    <header>
        <div class="header-content">
          <img src="./images/sortphy.png" alt="Sortphy Logo" class="logo">
          <div>
            <h1>Solucionador Interativo do Problema da Mochila</h1>
            <p>Feito por Sortphy - <a href="https://github.com/Sortphy" target="_blank">github.com/Sortphy</a></p>
          </div>
        </div>
      </header>


  <div class="container">
    <div class="intro">
      <h2>O Problema da Mochila</h2>
      <p>O problema da mochila é um desafio clássico de otimização: dado um conjunto de itens com valores e pesos específicos, determine quais itens incluir de forma que o peso total seja menor ou igual a um limite determinado (a capacidade da mochila) e que o valor total seja o maior possível.</p>
      <p>Esta ferramenta interativa permite que você explore o problema utilizando diferentes algoritmos de resolução, cada um com suas próprias características de eficiência e garantias de solução. Você pode comparar os resultados e o número de etapas necessárias para cada abordagem.</p>
    </div>

    <div class="flex-container">
      <div class="control-panel">
        <h3>Painel de Controle</h3>

        <div class="form-group">
          <label for="capacity-input">Capacidade da Mochila:</label>
          <input type="number" id="capacity-input" min="1" max="10000" value="10"
                 title="A capacidade da mochila afeta o desempenho dos algoritmos. Valores muito altos podem tornar alguns algoritmos lentos.">
          <small class="warning-text" id="capacity-warning" style="display: none; color: var(--warning);">
            ⚠️ Capacidade alta pode tornar alguns algoritmos lentos
          </small>
        </div>

        <div class="form-group">
          <label for="item-count">Número de Itens:</label>
          <input type="number" id="item-count" min="1" max="1000" value="5"
                 title="O número de itens afeta significativamente o tempo de execução. Algoritmos de força bruta são limitados a ~20 itens.">
          <small class="warning-text" id="items-warning" style="display: none; color: var(--warning);">
            ⚠️ Muitos itens podem tornar alguns algoritmos muito lentos
          </small>
        </div>

        <div class="form-group">
          <label>Valor dos Itens:</label>
          <div style="display: flex; gap: 1rem;">
            <div style="flex: 1;">
              <label for="min-value">Mínimo:</label>
              <input type="number" id="min-value" min="1" max="1000" value="1"
                     title="Valor mínimo para os itens">
            </div>
            <div style="flex: 1;">
              <label for="max-value">Máximo:</label>
              <input type="number" id="max-value" min="1" max="1000" value="10"
                     title="Valor máximo para os itens">
            </div>
          </div>
          <small class="warning-text" id="value-warning" style="display: none; color: var(--warning);">
            ⚠️ O valor mínimo não pode ser maior que o máximo
          </small>
        </div>

        <div class="form-group">
          <label>Peso dos Itens:</label>
          <div style="display: flex; gap: 1rem;">
            <div style="flex: 1;">
              <label for="min-weight">Mínimo:</label>
              <input type="number" id="min-weight" min="1" max="1000" value="1"
                     title="Peso mínimo para os itens">
            </div>
            <div style="flex: 1;">
              <label for="max-weight">Máximo:</label>
              <input type="number" id="max-weight" min="1" max="1000" value="7"
                     title="Peso máximo para os itens">
            </div>
          </div>
          <small class="warning-text" id="weight-warning" style="display: none; color: var(--warning);">
            ⚠️ O peso mínimo não pode ser maior que o máximo
          </small>
        </div>

        <button class="generate" id="generate-btn">Gerar Itens Aleatórios</button>

        <div class="form-group">
          <label>Algoritmo:</label>
          <select id="algorithm-select" title="Escolha o algoritmo baseado no tamanho do problema e na precisão desejada">
            <option value="bruteforce" title="Garante solução ótima, mas é muito lento com mais de 20 itens">Força Bruta</option>
            <option value="dp" title="Bom para problemas médios, complexidade O(n*W)">Programação Dinâmica</option>
            <option value="dp_recursive" title="Implementação recursiva com memoization">Programação Dinâmica (Recursiva)</option>
            <option value="greedy" title="Rápido mas não garante solução ótima">Algoritmo Guloso</option>
            <option value="bnb" title="Mais eficiente que força bruta, usa poda de ramos">Branch and Bound</option>
            <option value="ga" title="Bom para problemas grandes, usa evolução de população">Algoritmo Genético</option>
            <option value="sa" title="Bom para problemas grandes, pode escapar de ótimos locais">Simulated Annealing</option>
            <option value="aco" title="Inspirado no comportamento de formigas, bom para problemas de otimização combinatória">Ant Colony Optimization</option>
            <option value="pso" title="Baseado no comportamento de enxames, eficiente para otimização multimodal">Particle Swarm Optimization</option>
            <option value="cuckoo" title="Inspirado no comportamento do cuco, bom para exploração global">Cuckoo Search</option>
            <option value="approx" title="Rápido, garante pelo menos 50% do valor ótimo">Aproximação</option>
            <option value="fptas" title="Pode chegar arbitrariamente perto da solução ótima">FPTAS</option>
          </select>
          <small class="warning-text" id="algorithm-warning" style="display: none; color: var(--warning);">
            ⚠️ Este algoritmo pode ser lento com os parâmetros atuais
          </small>
        </div>

        <button class="solve" id="solve-btn">Encontrar Melhor Solução</button>
        <button id="reset-btn">Redefinir Seleção</button>
        <button id="show-steps-btn">Mostrar Etapas do Algoritmo</button>
        <button id="explain-algorithm-btn">Explicação do Algoritmo</button>

        <div class="capacity-status">
          <p>Peso Atual: <span id="current-weight">0</span>/<span id="max-capacity">10</span></p>
          <div class="capacity-bar">
            <div class="capacity-fill" id="capacity-fill"></div>
          </div>
        </div>
      </div>

      <div class="visualization">
        <h3>Itens</h3>
        <div class="items-container" id="items-container">
          <!-- Os itens serão gerados aqui -->
        </div>

        <h3>Sua Mochila</h3>
        <div class="placeholder-backpack" id="backpack">
          <span>Capacidade: 10</span>
        </div>

        <div class="current-selection">
          <h3>Seleção Atual</h3>
          <p>Valor: <span id="selection-value">0</span></p>
          <p>Peso: <span id="selection-weight">0</span></p>
          <div id="selected-items" class="items-container">
            <!-- Os itens selecionados aparecerão aqui -->
          </div>
        </div>
      </div>
    </div>

    <div class="result-panel" id="result-panel" style="display: none;">
      <h3>Solução Ótima</h3>
      <div class="optimal-solution" id="optimal-solution">
        <!-- A solução ótima será exibida aqui -->
      </div>

      <div class="result-stats">
        <div class="stat-card">
          <h4>Melhor Valor</h4>
          <div class="stat-value" id="best-value">0</div>
        </div>
        <div class="stat-card">
          <h4>Peso Total</h4>
          <div class="stat-value" id="total-weight">0</div>
        </div>
        <div class="stat-card">
          <h4>Etapas</h4>
          <div class="stat-value" id="steps-taken">0</div>
        </div>
        <div class="stat-card">
          <h4>Tempo de Execução</h4>
          <div class="stat-value" id="execution-time">0 ms</div>
        </div>
      </div>
    </div>

    <div class="algorithm-info">
      <h3>Sobre os Algoritmos</h3>
      <p>Cada algoritmo implementado tem características únicas:</p>
      <ul>
        <li><strong>Força Bruta:</strong> Garante a solução ótima mas é ineficiente para muitos itens (2^n combinações).</li>
        <li><strong>Programação Dinâmica:</strong> Eficiente para problemas com capacidade moderada (O(n*W)).</li>
        <li><strong>Programação Dinâmica (Recursiva):</strong> Usa recursividade com memoization para armazenar resultados em cache e evitar recálculos (O(n*W)).</li>
        <li><strong>Algoritmo Guloso:</strong> Rápido mas não garante solução ótima, usa razão valor/peso.</li>
        <li><strong>Branch and Bound:</strong> Mais eficiente que força bruta, usa poda de ramos.</li>
        <li><strong>Algoritmo Genético:</strong> Boa para problemas grandes, usa evolução de população.</li>
        <li><strong>Simulated Annealing:</strong> Boa para problemas grandes, pode escapar de ótimos locais.</li>
        <li><strong>Ant Colony Optimization:</strong> Inspirado no comportamento de formigas, usa feromônios e heurísticas para explorar soluções promissoras.</li>
        <li><strong>Particle Swarm Optimization:</strong> Baseado no comportamento de pássaros e peixes em grupos, cada partícula se move no espaço de busca influenciada por soluções pessoais e globais.</li>
        <li><strong>Cuckoo Search:</strong> Inspirado no comportamento parasita do cuco, combina voos de Lévy para busca global e abandono de ninhos para diversificação.</li>
        <li><strong>Aproximação:</strong> Rápido, garante pelo menos 50% do valor ótimo.</li>
        <li><strong>FPTAS:</strong> Pode chegar arbitrariamente perto da solução ótima.</li>
      </ul>
    </div>
  </div>

  <div class="modal" id="steps-modal">
    <div class="modal-content">
      <span class="close-modal" id="close-modal">&times;</span>
      <h2>Etapas do Algoritmo</h2>
      <p>Esta visualização mostra como o algoritmo selecionado funciona para resolver o problema da mochila.</p>

      <div class="visual-steps" id="visual-steps">
        <!-- As etapas serão exibidas aqui -->
      </div>

      <h3>Detalhes da Execução</h3>
      <div class="combinations-display" id="combinations-display">
        <!-- Os detalhes serão exibidos aqui -->
      </div>
    </div>
  </div>

  <div class="modal" id="explanation-modal">
    <div class="modal-content">
      <span class="close-modal" id="close-explanation-modal">&times;</span>
      <h2 id="explanation-title">Explicação do Algoritmo</h2>
      <div id="algorithm-explanation" class="algorithm-explanation">
        <!-- O conteúdo será preenchido dinamicamente -->
      </div>
    </div>
  </div>


</body>
</html>