문제
옷을 정가 이하로 바겐세일 하는 가게에 갔다.
그 가게에서, 현재 가지고 있는 현금(P)
이내에서, 최대 가치가되게(=정가 기준 합이 가장 크게) 옷을 구매하는 방법을 제시하시오.
단, 구매할 수 있는 옷의 수량 한도내에서
구매해야 함(L)
- 가치: 옷의 정가 (values)
- 판매가격: 현재 옷의 가격 (prices)
목표: 전체 구매한 옷의 정가 합이 최대가 되도록
제약조건: 가지고 있는 현금 이내라야함. P >= Sum(옷의 판매가격)
구매한도 개수 이내라야 함. L >= 구매한 옷의 수량
입력파일(Clothes.in)
<형태>
문제개수(T)
옷_개수(N) 보유현금(P)
개수한계(L)
판가1 판가2 ... 판가(N)
정가1 정가2 ... 정가(N)
8
4 12 4
5 4 6 3
10 40 30 50
4 12 2
5 4 6 3
10 40 30 50
3 30 3
5 10 20
50 60 140
3 50 3
10 20 30
60 100 120
5 20 5
2 3 4 5 9
3 4 5 8 10
30 60 30
2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9
3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20
30 60 20
2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9
3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20
50 100 50
2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9
3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20
출력 형태
Test #1
구매 옷 리스트:4 2 1
총 구매 가격:12
총 정가:100
Elapsed:1ms
작성방법
제시된 Clothes.java를 기초로해서 작성하시오.
수행시간: 50ms 이내.
//Clothes.java
package dynamic;
import java.io.File;
import java.util.ArrayList;
import java.util.Scanner;
public class Clothes {
public static void main(String[] args) throws Exception {
long t1, t2;
Scanner sc = new Scanner(new File("res/Clothes.in"));
int T;
T = sc.nextInt();
int N = 0; // 옷 개수
int P = 0; // 보유현금
int L = 0; // 구매가능한 개수
int[] prices = null; // 판가
int[] values = null; // 정가
for (int testNum = 1; testNum <= T; testNum++) {
N = sc.nextInt();
P = sc.nextInt();
L = sc.nextInt();
prices = new int[N + 1]; // 판가
for (int i = 1; i <= N; i++) {
prices[i] = sc.nextInt();
}
values = new int[N + 1]; // 정가
for (int i = 1; i <= N; i++) {
values[i] = sc.nextInt();
}
t1 = System.currentTimeMillis();
int[] purchaseList = getPurchaseList(N, P, L, prices, values);
t2 = System.currentTimeMillis();
System.out.println("Test #" + testNum);
printPurchaseList(purchaseList, prices, values);
System.out.println("Elapsed:" + (t2 - t1) + "ms");
System.out.println("");
}
sc.close();
}
private static void printPurchaseList(int[] list, int[] prices, int[] values) {
if (list == null || list.length == 0) {
System.out.println("fail");
return;
}
StringBuffer sb = new StringBuffer();
long totalPurchasingPrice = 0;
long totalValue = 0;
for (int i = 0; i < list.length; i++) {
sb.append(list[i] + " ");
totalPurchasingPrice += prices[list[i]];
totalValue += values[list[i]];
}
System.out.println("구매 옷 리스트:" + sb.toString());
System.out.println("총 구매 가격:" + totalPurchasingPrice);
System.out.println("총 정가:" + totalValue);
}
private static int[] getPurchaseList(int n, int p, int l, int[] prices, int[] values) {
return null;
}
}
--------------------------------------------------------------------------------------
***********************************************************************************************************
--------------------------------------------------------------------------------------
풀이
배낭문제를 응용해서 만든 문제이다. 따라서, 배낭문제를 잘 이해할 수 있다면, 쉽게 풀 수 있는 문제이다.
배낭문제의 경우는, 주어진 보석들에 대해서, 허용된 무게만큼의, 최대가치가 되는 보석을 선택하는 것이다.
옷 문제는, 주어진 옷들에 대해서, 허용된 가격만큼의, 허용된 개수 만큼의, 최대가치(=정가)가 되는 옷을 선택하는 것이다.
조건이 하나 더 늘어난 것이다.
점화식을 만들어 보자.
최대가치를 나타내는 함수를 V라하고, 옷의 개수는 i, 허용된 가격은 p, 허용된 개수는 l 이라 하면,
V(i,p,l) = (p >= prices[i] && l >= 1) ? max(V(i-1,p,l),V(i-1,p-prices[i],l-1)+val[i]) : V(i-1,w,l)
참조로, 배낭문제에서의 점화식과 비교해보면 이해가 될 것이다.
V(i,w) = (w >= wt[i]) ? max(V(i-1,w), V(i-1,w-wt[i]) + val[i]) : V(i-1,w)
따라서, 이를 구현하면 다음과 같이 된다. (먼저 재귀형태로 생각해보고, 재귀형태의 호출이 중복되지 않도록 메모이제이션을 하는 순으로 작성해야 한다. )
private static int purchase_table(int n, int p, int l,
int[] prices, int[] values, int[][][] table) {
if (n <= 0 || p <= 0 || l <= 0) {
return 0;
}
if ((n > 1) && (table[n - 1][p][l] == 0)) {
table[n - 1][p][l] = purchase_table(n - 1, p, l, prices, values, table);
}
if ((n > 1 && p > prices[n] && l > 1) && (table[n - 1][p - prices[n]][l - 1] == 0)) {
table[n - 1][p - prices[n]][l - 1] =
purchase_table(n - 1, p - prices[n], l - 1, prices, values, table);
}
if ((prices[n] <= p && l >= 1) &&
(table[n - 1][p][l] < table[n - 1][p - prices[n]][l - 1] + values[n])) {
table[n][p][l] = table[n - 1][p - prices[n]][l - 1] + values[n];
} else {
table[n][p][l] = table[n - 1][p][l];
}
return table[n][p][l];
}
얻어진 table로부터, 어떤 옷이 선택되었는 지를 트레이싱하는 것은 다음과 같다.
private static int[] extract(int[][][] V, int P, int L, int[] prices) {
ArrayList<Integer> list = new ArrayList<Integer>();
int p = P;
int l = L;
for (int i = V.length - 1; i >= 1; i--) {
if (p >= 0 && l >= 0 && V[i][p][l] != V[i - 1][p][l]) {
list.add(i);
p = p - prices[i];
l = l - 1;
}
}
int[] a = new int[list.size()];
for (int i = 0; i < a.length; i++) {
a[i] = list.get(i);
}
return a;
}
전체소스는 아래와 같고, 여기에는 위와 같이 메모이제이션을 이용한 방법과 함께, bottom up으로 테이블 전체값을 얻어내서 구하는 방식 모두 구현되어 있다.
소스
package dynamic;
import java.io.File;
import java.util.ArrayList;
import java.util.Scanner;
public class Clothes {
public static void main(String[] args) throws Exception {
long t1, t2;
Scanner sc = new Scanner(new File("res/Clothes.in"));
int T;
T = sc.nextInt();
int N = 0; // 옷 개수
int P = 0; // 보유현금
int L = 0; // 구매가능한 개수
int[] prices = null; // 판가
int[] values = null; // 정가
for (int testNum = 1; testNum <= T; testNum++) {
N = sc.nextInt();
P = sc.nextInt();
L = sc.nextInt();
prices = new int[N + 1]; // 판가
for (int i = 1; i <= N; i++) {
prices[i] = sc.nextInt();
}
values = new int[N + 1]; // 정가
for (int i = 1; i <= N; i++) {
values[i] = sc.nextInt();
}
t1 = System.currentTimeMillis();
int[] purchaseList = getPurchaseList(N, P, L, prices, values);
t2 = System.currentTimeMillis();
System.out.println("Test #" + testNum);
printPurchaseList(purchaseList, prices, values);
System.out.println("Elapsed:" + (t2 - t1) + "ms");
System.out.println("");
}
sc.close();
}
private static void printPurchaseList(int[] list, int[] prices, int[] values) {
if (list == null || list.length == 0) {
System.out.println("fail");
return;
}
StringBuffer sb = new StringBuffer();
long totalPurchasingPrice = 0;
long totalValue = 0;
for (int i = 0; i < list.length; i++) {
sb.append(list[i] + " ");
totalPurchasingPrice += prices[list[i]];
totalValue += values[list[i]];
}
System.out.println("구매 옷 리스트:" + sb.toString());
System.out.println("총 구매 가격:" + totalPurchasingPrice);
System.out.println("총 정가:" + totalValue);
}
private static int[] getPurchaseList(int n, int p, int l, int[] prices, int[] values) {
int[][][] V = new int[n + 1][p + 1][l + 1];
//purchase(n, p, l, prices, values, V);
purchase_table(n, p, l, prices, values, V);
return extract(V, p, l, prices);
}
private static int[] extract(int[][][] V, int P, int L, int[] prices) {
ArrayList<Integer> list = new ArrayList<Integer>();
int p = P;
int l = L;
for (int i = V.length - 1; i >= 1; i--) {
if (p >= 0 && l >= 0 && V[i][p][l] != V[i - 1][p][l]) {
list.add(i);
p = p - prices[i];
l = l - 1;
}
}
int[] a = new int[list.size()];
for (int i = 0; i < a.length; i++) {
a[i] = list.get(i);
}
return a;
}
private static int purchase_table(int n, int p, int l, int[] prices,
int[] values, int[][][] table) {
if (n <= 0 || p <= 0 || l <= 0) {
return 0;
}
if ((n > 1) && (table[n - 1][p][l] == 0)) {
table[n - 1][p][l] = purchase_table(n - 1, p, l, prices, values, table);
}
if ((n > 1 && p > prices[n] && l > 1) && (table[n - 1][p - prices[n]][l - 1] == 0)) {
table[n - 1][p - prices[n]][l - 1] =
purchase_table(n - 1, p - prices[n], l - 1, prices, values, table);
}
if ((prices[n] <= p && l >= 1) &&
(table[n - 1][p][l] < table[n - 1][p - prices[n]][l - 1] + values[n])) {
table[n][p][l] = table[n - 1][p - prices[n]][l - 1] + values[n];
} else {
table[n][p][l] = table[n - 1][p][l];
}
return table[n][p][l];
}
private static int purchase(int N, int P, int L, int[] prices, int[] values, int[][][] V) {
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= P; j++) {
for (int k = 1; k <= L; k++) {
if ((prices[i] <= j) &&
(V[i - 1][j][k] < V[i - 1][j - prices[i]][k - 1] + values[i])) {
V[i][j][k] = V[i - 1][j - prices[i]][k - 1] + values[i];
} else {
V[i][j][k] = V[i - 1][j][k];
}
}
}
}
return V[N][P][L];
}
}
실행결과
Test #1
구매 옷 리스트:4 2 1
총 구매 가격:12
총 정가:100
Elapsed:0ms
Test #2
구매 옷 리스트:4 2
총 구매 가격:7
총 정가:90
Elapsed:0ms
Test #3
구매 옷 리스트:3 2
총 구매 가격:30
총 정가:200
Elapsed:0ms
Test #4
구매 옷 리스트:3 2
총 구매 가격:50
총 정가:220
Elapsed:0ms
Test #5
구매 옷 리스트:5 4 3 1
총 구매 가격:20
총 정가:26
Elapsed:0ms
Test #6
구매 옷 리스트:30 28 27 26 21 20 18 17 16 11 10 8 7 6 1
총 구매 가격:60
총 정가:132
Elapsed:3ms
Test #7
구매 옷 리스트:30 28 27 26 21 20 18 17 16 11 10 8 7 6 1
총 구매 가격:60
총 정가:132
Elapsed:2ms
Test #8
구매 옷 리스트:50 48 47 46 40 38 37 36 30 28 27 26 20 18 17 16 14 10 8 7 6 4
총 구매 가격:100
총 정가:221
Elapsed:13ms
-끝
'알고리즘 > 알고리즘(Java)' 카테고리의 다른 글
| 25. [다이나믹]효율적인 행렬곱 순서 (0) | 2015.04.26 |
|---|---|
| 24.[다이나믹]조립라인 스케줄링(Assembly Line Scheduling) (0) | 2015.04.25 |
| 22. [다이나믹]배낭 문제 (Knapsack problem) (0) | 2015.04.21 |
| 21. [다이나믹] 최소 공정시간 찾기 (0) | 2015.04.21 |
| 20. [다이나믹] 행렬 경로 문제 (0) | 2015.04.16 |