728x90
반응형
[동적 계획법, 분할과 정복]
-> 이진 탐색
-> 최단 경로([다익스트라 알고리즘] -> [벨만-포드 알고리즘] )
-> [탐욕 알고리즘 (Greedy) -> 냅색 알고리즘]
-> 최소신장트리 ([크루스칼 알고리즘] -> [프림 알고리즘])
-> 백트래킹
[동적 계획법, 분할과 정복]
-> 이진 탐색
-> 최단 경로([다익스트라 알고리즘] -> [벨만-포드 알고리즘] )
-> [탐욕 알고리즘 (Greedy)] -> 냅색 알고리즘
package org.algorithms.dp.greedyAndKnapsack;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CoinExchange {
//탐욕 알고리즘(그리디) - 근사치 추정
//: 최적의 해에 가까운 값을 구하기 위해 사용되며,
//여러 경우의 수 중 하나를 선택하는 경우, 매순간 최적이라고 생각되는 (현재 시점의 최고의 선택)으로 진행해 최종 결과 반환
//한계 : 여러 조합의 경우의 수가 존재한다면, 최적이 아닌 경우의 수도 존재
//동전 교환
public void coinFunc(Integer price, List<Integer> coinList){
Integer totalCoinCount=0;
Integer coinNum=0;
List<Integer> details =new ArrayList<>();
for(int i : coinList){
coinNum=price/i;
totalCoinCount+=coinNum;
price-=coinNum*i;
details.add(coinNum);
System.out.println(i+"원: "+coinNum+"개");
}
System.out.println("총 동전 개수 : "+totalCoinCount);
}
public static void main(String[] args) {
CoinExchange gObject = new CoinExchange();
List<Integer> coinList = new ArrayList<Integer>(Arrays.asList(500, 100, 50, 1));
gObject.coinFunc(4720, coinList);
}
}
package org.algorithms.dp.greedyAndKnapsack;
import java.util.Arrays;
import java.util.Comparator;
public class FractionalKnapsack {
//부분 배낭 알고리즘
//:무게 제한이 k인 배낭에 최대 가치를 가지는 물건을 넣는 문제
//각 물건은 무게 w와 가치 v로 표현한다.
//물건을 쪼개서 일부분을 배낭에 넣을 수도 있다.
//: 무게 대비 가치가 높은 물건을 넣는다. -> 가치/무게의 비율이 높은 물건순
//현재 시점에 가장 가치가 높은 물건 선택
public void fknapsack(Integer[][] objectList, double capacity){
double totalValue = 0.0;
double fraction = 0.0;
//가치/무게 순으로 정렬하기 위해 재정의
Arrays.sort(objectList, new Comparator<Integer[]>() {
@Override
public int compare(Integer[] o1, Integer[] o2) {
return o2[1]/o2[0]-o1[1]/o1[0];
}
});
for(Integer[] arr:objectList){
if(capacity-(double) arr[0]>0){
capacity-=(double) arr[0];
totalValue+=(double) arr[1];
System.out.println("무게: "+arr[0]+" , 가치: "+ arr[1]);
}else{
fraction=capacity/(double) arr[0];
totalValue+=(double) arr[1]*fraction;
System.out.println("무게: "+arr[0]+" , 가치: "+arr[1]+" , 비율: "+fraction);
//나머지 비율까지 모두 채웠으므로 중단
break;
}
}
System.out.println("총 담을 수 있는 가치: "+totalValue);
}
public static void main(String[] args) {
FractionalKnapsack fractionalKnapsack=new FractionalKnapsack();
Integer[][] objectList = {{10,10}, {15,12},{20,10},{25,8},{30,5}};
fractionalKnapsack.fknapsack(objectList,30.0);
}
}
-> 최소신장트리 ([크루스칼 알고리즘] -> [프림 알고리즘])
-> 백트래킹
728x90
반응형
'Server Programming > BackEnd Project' 카테고리의 다른 글
숫자 짝꿍-String.repeat, append, String=char+"", startsWith("0"), char-48=숫자 (0) | 2023.02.06 |
---|---|
로또의 최고 순위와 최저 순위 - Collections.frequncy, Collectors.toList(), boxed().toArray(Integer[]::new); (0) | 2023.02.06 |
정규표현식과 matches, patterns 메서드, 진법 변환 (0) | 2023.02.03 |
51일차 - TIL (0) | 2023.02.01 |
50일차 - TIL (0) | 2023.02.01 |