개인 공간

출처 : http://devils9curse.tistory.com/11

냅색 문제라는 것이 있습니다.

주어진 가방이 있을 때 가치가 최대한이 되도록 물건을 담는 것이죠.

그런데 각 물건은 무게가 있어서, 원하는 만큼 전부 가방에 담을 수는 없습니다.

이런 냅색 문제에는 여러가지 종류가 있는데요, 거의 대부분 다이나믹으로 해결할 수 있습니다.

우선 한 물건당 물건의 수량이 1개밖에 없고 물건을 쪼갤 수도 없는 0/1 냅색이 있습니다.

이 경우의 다이나믹 테이블 정의와 점화식은 다음과 같습니다.
(W[i]:i번째 물건의 무게, P[i]:i번째 물건의 가치

D[i][j]:i물건까지를 j크기의 가방에 담았을 때 최대 가치
D[i][j]=MAX(D[i-1][j],D[i-1][j-W[i]]+P[i]) :(j>=W[i])
=D[i-1][j] :(j<W[i])

01Knapsack.cpp

그리고 물건을 쪼갤 수는 없지만 물건의 수량이 여러개인 경우로 변형을 할 수 있는데요,

일단 물건의 개수가 유한개로 주어진 경우에는 두가지 풀이가 있습니다.

하나는 각 물건당 여러개를 담았을 때의 무게와 가치를 전부 데이터에 넣어서 0/1 냅색을 하는 것이죠.

또 다른 방법은, 다이나믹을 약간 다르게 돌리는 것입니다.

D[i][j]:i물건까지를 j크기의 가방에 담았을 때 최대 가치
D[i][j]=MAX(D[i-1][j],D[i-1][j-W[i]*k]+P[i]*k) :(j>=W[i]*k)
=D[i-1][j] :(j<W[i]*k)

별 차이는 없죠?

물건의 개수가 무한개로 주어지는 경우를 보겠습니다.

이번에는 1차원 다이나믹만으로도 해결이 가능합니다.

D[j]:j크기의 가방에 담았을 때 최대 가치
D[j]=MAX(D[j],D[j-W[i]]+P[i]) (j>=W[i])

Knapsack.cpp

마지막 경우로는, 물건을 쪼갤 수 있는 경우가 되겠는데요, 이런 경우에는 그리디로도 해결이 가능합니다.

무게 1당 가치가 높은 순으로 넣을 수 있는 만큼 차례대로 넣으면 되죠.

냅색 문제는 여러 방법으로도 활용이 가능하니, 잘 알아 두시는 것이 좋습니다.

/- 프로그램 명 : 단위 크기의 정사각형에 있는 N개의 점에 대한 순서쌍 중 몇 개가 d 보다 작은 거리를 갖는지 알아보기 *-

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include "Point.h"

/- Point.h

typedef struct Point{

float x, y;

} Point;

*-

typedef struct node *link;

struct node{

point p;

link next;

};

link **grid; // 격자

int G;

float d; // 거리

int cnt = 0; // count

gridinsert(float x, float y)

{

int i, j;

link s;

int X = x*G + 1, Y = y*G + 1; // 삽입할 데이터의 범위(격자위치)를 찾는다.

link t = (link*) calloc(1, sizeof(*t));

t->p.x = x, t->p.y = y;

for(i = X-1; i <= X+1; i++)

for(j = Y-1; j <= Y+1; j++)

for(s = grid[i][j]; s != NULL; s = s->next)

// d 거리 이내일 경우 개수를 더한다.

if(distance(s->p, t->p) < d)

cnt++;

// 데이터를 격자 범위에다 삽입한다.

t->next = grid[X][Y], grid[X][Y] = t;

}

link **malloc2d(int r, int c) // 이차원 calloc(malloc)

{

int i;

link **t = (link**) calloc(r, sizeof(*t));

for(i=0; i<r; i++)

t[i] = (link*) calloc(c, sizeof(*t[i]));

return t;

}

int main(void)

{

int i, j, N;

scanf("%d %f", &N, &d);

G = 1/d, grid = malloc2d(G+3, G+3);

// grid 생성, G 는 격자 범위를 나타내는 수

for(i=0; i < G+3; i++)

for(j=0; j < G+3; j++)

grid[i][j] = NULL;

for(i=0; i < N; i++)

gridinsert(randFloat(), randFloat());

// 데이터 삽입 randFloat 함수는 return 1.0 * rand()/RAND_MAX; 한다

printf("%d edges shorter than %f\n", cnt, d);

return 0;

}