비용을 가지는 배낭

비용을 가지는 배낭

배낭 크기 5000
물건크기={3000,2000,1000}
각각비용={1,2,3}

배낭을 가득 채울때 비용을 최대로 할때 그 비용은?




풀이 전략
1. 물건을 조합하는 방법에 대해 전체 탐색으로 구현하기
bagsize=5000
N=3(물건갯수)
size={3000,2000,1000}
cost={1,2,3}
--------------------------------
3000
3000,2000
3000,1000
3000,2000,1000

2000
2000,1000

1000
--------------------------------
위의 내용을 단순 for loop로 구현
index로 놓고 보면
null,null,null
[0],null,null
[0],[1],null
[0],null,[2]
[0],[1],[2]
null,[1],null
null,[1],[2]
null,null,[2]
--------------
for(i=-1;i<N;i++){
  for(j=-1;j<N;j++){

    for(k=-1;k<N;k++){
      if( i != -1 ) add(i)
      if( j != -1 ) add(j)
      if( k != -1 ) add(k)
      이런식으로 N개의 loop로 계산하면 쉬우나 N이 가변적이라 구현의 어려움

--------------

다른 방법으로 tree형태로 고민해볼 수 있다.

즉 처음 index 0을 선택하느냐 안하느냐에 따라 2가지가 나뉘고

그후 index 1을 선택하느냐 안하느냐에 따라 2가지가 나뉜다. (0 미선택 1 선택)

              1             0       index 0 

          1      0      1     0    index 1

        1  0   1 0   1 0   1 0   index 2

이것을 순회하는 방법은 DFS,BFS가 있습니다.

깊이 우선인 DFS는 스택으로 구현이 됩니다.

소스는 이렇게 되며, 순수하게 조합하는 방법에 대한 소스 입니다.

#include <stdio.h>

#define N 3
int bag[N]={-1};
int size[N]={5000,3000,1000};

int DFS(int level,int item)      
{
  if(level>=0) {
   if( item == 0) bag[level]=-1;
   else bag[level]=size[level];
  }
  if(level >= N-1) { 
    int i;
    for(i=0;i<N;i++){
      printf("%d ",bag[i]);
    }
    printf("\n");
    return 0; 
  }
  DFS(level+1,0);
  DFS(level+1,1);
  return 0;
}

int main(void) {
 DFS(-1,0);
 return 0;
}

실행 결과

-1 -1 -1 
-1 -1 1000 
-1 3000 -1 
-1 3000 1000 
5000 -1 -1 
5000 -1 1000 
5000 3000 -1 
5000 3000 1000 

2. 그 중에 배낭크기 보다 커진다면 중단
마지막 노드에서 배낭크기의 합을 출력하도록 한다.

#include <stdio.h>

#define N 3
int bagsize=5000;
int bag[N]={-1};
int size[N]={5000,3000,1000};

int DFS(int level,int item,int sum)    
{
  if(level>=0) {
   if( item == 0){
    bag[level]=-1; 
   }
   else {
    bag[level]=size[level];
    sum+=size[level];
   }
  }
  if(level >= N-1) {
    int i;
    for(i=0;i<N;i++){
      printf("%d ",bag[i]);
    }
    printf("sum %d\n",sum);
    return 0;
  }
  DFS(level+1,0,sum);
  DFS(level+1,1,sum);
  return 0;
}

int main(void) {
 DFS(-1,0,0);
 return 0;
}

실행화면
Success time: 0 memory: 2160 signal:0

-1 -1 -1 sum 0
-1 -1 1000 sum 1000
-1 3000 -1 sum 3000
-1 3000 1000 sum 4000
5000 -1 -1 sum 5000
5000 -1 1000 sum 6000
5000 3000 -1 sum 8000
5000 3000 1000 sum 9000

미리 DFS탐색을 중지하고 다음 탐색을 하기위해서는 중간마다 총수치를 계산해야 한다.

bagsize < sum+size[level] 조건을 추가하였다. 이번에 추가되는 크기가 커진다면 level을 더 진입 하지 않도록 한다.

#include <stdio.h>

#define N 3
int bagsize=5000;
int bag[N]={-1};
int size[N]={5000,3000,1000};

int DFS(int level,int item,int sum)    
{
  if(level>=0) {
   if(item == 0){
    bag[level]=-1; 
   }
   else {
#if 1
    if( bagsize < sum+size[level] ) {
      int i;
      for(i=0;i<level;i++){
        printf("%d ",bag[i]);
      }
      printf("sum %d\n",sum);
      return 0;
    }
#endif
    bag[level]=size[level];
    sum+=size[level];
   }
  }
  if(level >= N-1) {
    int i;
    for(i=0;i<N;i++){
      printf("%d ",bag[i]);
    }
    printf("sum %d\n",sum);
    return 0;
  }
  DFS(level+1,0,sum);
  DFS(level+1,1,sum);
  return 0;
}

int main(void) {
 DFS(-1,0,0);
 return 0;
}

Success time: 0 memory: 2160 signal:0

-1 -1 -1 sum 0
-1 -1 1000 sum 1000
-1 3000 -1 sum 3000
-1 3000 1000 sum 4000
5000 -1 -1 sum 5000
5000 -1 sum 5000
5000 sum 5000

3. 비용도 고려하기

sum 계산하는 위치에 cost계산도 같이 하면 쉽게 처리할 수 있다.

#include <stdio.h>

#define N 3
int bagsize=5000;
int bag[N]={-1};
int size[N]={5000,3000,1000};
int cost[N]={3,2,1};

int maxcost = 0;

int DFS(int level,int item,int sum,int sumcost)    
{
  if(level>=0) {
   if(item == 0){
    bag[level]=-1; 
   } else {
    if( bagsize < sum+size[level] ) {
      int i;
      for(i=0;i<level;i++){
        printf("%5d ",bag[i]);
      }
      printf("/sum %5d costsum %5d costmax %5d\n",sum,sumcost,maxcost);
      return 0;
    }
    bag[level]=size[level];
    sum+=size[level];
    sumcost+=cost[level];
    if( maxcost < sumcost ) maxcost = sumcost;
   }
  }
  
  if(level >= N-1) {
    int i;
    for(i=0;i<N;i++){
      printf("%5d ",bag[i]);
    }
    printf("sum %5d costsum %5d costmax %5d\n",sum,sumcost,maxcost);
    return 0;
  }
  DFS(level+1,0,sum,sumcost);
  DFS(level+1,1,sum,sumcost);
  return 0;
}

int main(void) {
 DFS(-1,0,0,0);
 return 0;
}

                                                                                      
   -1    -1    -1 sum     0 costsum     0 costmax     0                                                                                                                                               
   -1    -1  1000 sum  1000 costsum     1 costmax     1                                                                                                                                               
   -1  3000    -1 sum  3000 costsum     2 costmax     2                                                                                                                                               
   -1  3000  1000 sum  4000 costsum     3 costmax     3                                                                                                                                               
 5000    -1    -1 sum  5000 costsum     3 costmax     3                                                                                                                                               
 5000    -1 /sum  5000 costsum     3 costmax     3                                                                                                                                                    
 5000 /sum  5000 costsum     3 costmax     3