배낭 문제(Knapsack Problem냅색 프라블럼[*])는조합 최적화의 유명한 문제이다.간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최대값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.
이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를0-1 배낭문제(0-1Knapsack Problem)라 부른다.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
public class Knapsack {
Knapsack(String path) throws FileNotFoundException {
Scanner input = new Scanner(new File(path));
int n = input.nextInt();// 물건의 갯수
int W = input.nextInt();// 용량
Item item[] = new Item[n];// 무게
Queue<Item> q=new LinkedList<Item>();
// 리턴할 최대 가치.
int max_p = 0;
// 없어도 됨. 그냥 쓸데없이 많이 검색하지 않기 위해서
int max_w = 0;
Property w[] = new Property[W + 1];// 가치가 저장됨
for (int i = 0; i < W + 1; i++) {
w[i] = new Property();
}
for (int i = 0; i < n; i++) {
item[i] = new Item(input.nextInt(), input.nextInt());
}
// 편의상 정렬
Arrays.sort(item);
// 초기화
max_w = item[0].w;
//System.out.println("mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm");
for (int i = 0; i < n; i++) {
if (max_w < item[i].w) {
max_w = item[i].w;
}
//어떤 무게 x 일때의 최대 가치는 w[x].sum_p 가 된다.
//만약 w[x].sum_p 가 바뀔때는 새로운 가치 값이 더 클때이다.
if (w[item[i].w].sum_p < item[i].p) {
q.add(new Item(item[i].p,item[i].w));
}
for (int j = item[0].w; j <= max_w && j <= W - item[i].w; j++) {
//기존에 저장되어있는 (j + item[i].w) 무게의 가치
int p1 = w[j + item[i].w].sum_p;
//새로 추가할지 알아볼 (j + item[i].w) 무게의 가치
int p2 = w[j].sum_p + item[i].p;
if (w[j].flag >= 0 && w[j].flag < i) {
//만약 플레그가 0보다 작으면. 즉 한번도 기록한적이 없으면 새로 기록.
if (w[j + item[i].w].flag < 0) {
w[j + item[i].w].flag = i;
w[j + item[i].w].sum_p = p2;
if (max_p < p2)
max_p = p2;
} else {
//기존에 있던 가치가 새로 기록할 가치보다 낮다면 갈아치움
if (p1 < p2) {
//하지만 다른 조합에서 더 높은 가치가 나올수 있기때문에 기록은 전부 다 체크 한다음에 기록함.
q.add(new Item(p2,j + item[i].w));
if (max_p < p2)
max_p = p2;
}
}
}
if (max_w < j + item[i].w) {
max_w = j + item[i].w;
}
}
System.out.println(q.size());
while(!q.isEmpty())
{
Item it=q.remove();
w[it.w].flag=i;
w[it.w].sum_p=it.p;
}
}
//System.out.println("mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm");
for (int i = item[0].w; i <= max_w && i <= W; i++) {
if (w[i].flag >= 0) {
System.out.println(w[i].sum_p + "," + i);
}
}
System.out.println(max_p);
}
class Property {
public int sum_p = 0;
public int flag = -1;
Property() {
}
}
class Item implements Comparable<Item> {
int w;
int p;
Item(int p, int w) {
this.w = w;
this.p = p;
}
@Override
public int compareTo(Item o) {
return w - o.w;
}
public String toString() {
return "p=" + p + " w=" + w;
}
}
public static void main(String[] args) {
try {
new Knapsack("d:/input/knapsack-input.txt");
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
knapsack-input.txt