Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- MIPS
- Algorithm
- DS
- javascript
- Java
- Pipelining
- DoM
- system
- for
- DB
- web
- Class
- react
- instruction
- html
- data structure
- while
- python
- control
- MacOS
- XML
- computer
- architecture
- DATAPATH
- mysql
- github
- function
- Linux
- CSS
- php
Archives
- Today
- Total
목록knapsack (1)
YYYEJI
[Algorithm] 배낭문제, 냅색(Knapsack)이란?
Knapsack이란? 냅색(Napsack) 문제는 배낭에 담을 수 있는 무게 한계가 정해져 있고, 각각의 물건들은 무게와 가치가 정해져 있을 때, 배낭에 담을 수 있는 최대 가치의 합을 구하는 문제입니다. 배낭문제는 대표적으로 두 가지 종류로 나뉩니다. 1. 0-1 knapsack problem: 각각의 물건은 단 하나씩만 존재하며, 배낭에 담거나 담지 않거나 둘 중 하나의 선택만 가능하다. 2. Fractional knapsack problem: 각각의 물건은 무게에 비례하여 일부분만 담을 수 있으며, 물건을 자를 수 있다. Branch and Bound Branch and Bound는 최적화 문제를 풀기 위한 알고리즘으로 가능한 모든 해를 차는 대신, 최적의 해를 빠르게 찾기 위해 탐색 범위를 줄이는..
Algorithm
2023. 4. 18. 22:32