일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- 최단 경로
- 배열
- php
- 자바 스프링
- 플러터 개발환경 설정
- 자바
- Flutter
- php 프로그래밍 입문 솔루션
- Java
- php 프로그래밍 입문 3판
- 페이코 추천인코드
- 페이코 초대코드
- 스프링
- 페이코 친구코드
- C언어
- php 프로그래밍 입문 문제풀이
- SWEA
- C
- JAVA SPRING
- php 프로그래밍
- 한정 분기
- php 프로그래밍 입문
- programmers
- php 프로그래밍 입문 예제
- 파이썬
- 플러터
- php 프로그래밍 입문 연습문제
- 페이코 추천인
- spring
- 백준
Archives
- Today
- Total
05-19 04:57
목록0-1 Knapsack Problem 최고 우선 검색 (1)
ImJay
0-1 Knapsack Problem - 최고 우선 검색을 사용한 한정분기 (Branch and Bound)
0-1 Knapsack Problem 최고 우선 검색을 사용한 한정분기 (Branch and Bound) 서론 한정 분기 전략의 동기 : 되추적의 비효율되추적의 탐색 과정에서 Valid가 적용되더라도 여전히 상당한 비율의 정점을 방문하지 않아도 됨을 발견 되추적의 비효율 해결책 : 각 노드를 방문할 때마다 한계치(bound)를 계산 한계치(Bound) : 해당 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계 값 0/1 Knapsack Problem의 최고 우선 검색을 사용한 한정분기(Branch and Bound) 전략 1. 그 노드의 profit과 weight를 계산한다. 2. 그 노드의 bound를 계산한다. 3. 현재 노드의 profit이 maxprofit보다 크면 maxpr..
파이썬
2022. 6. 15. 22:42