알고리즘 과제로 0-1배낭채우기와 Fractional 배낭채우기를 구현..
일단 두 문제에 대해서 간단히 짚고 넘어 가자면 0-1배낭채우기란 배낭에 넣을 아이템을 쪼갤 수 없다. 반면 Fractional 배낭채우기란 배낭에 넣을 아이템을 쪼갤 수 있다. 이 두가지의 차이를 빼면 이후에 조건은 배낭의 아이템을 넣어 최대의 이익을 얻는 문제다.
0-1배낭채우기는 동적계획법을 이용해서 구현했고, Fractional 배낭채우기는 Greedy알고리즘을 이용해서 구현 했다. 그리고 두 알고리즘의 비교를 위해 각각의 알고리즘의 수행 속도를 결과에 포함 시켰다.
아래 실행화면...
invalid-file파일불러오기 버튼으로 데이터가 저장된 파일을 불러와서 시작버튼으로 수행하면 된다.
입력 데이터를 만들 때 입력 데이터 형식을 맞춰 줘야되는데 입력 데이터 형식은 첫번째 줄에는 항목의 수, 두번째 줄에는 배낭의 용량, 세번째 줄에는 항목들의 이익, 네번째줄에는 항목들의 무게..
예)
3
15
10 3 20
5 8 10
이런 식으로 맞춰줘야한다.
첨부된 파일에 기본 입력데이타set 3개도 포함시켜 뒀다.
p.s. win32로 만들어서 노가다도 좀들었고, 생각보다 UI가 이쁘지 않게 나왔다. mfc를 보던지 해야지..ㅋ
