8개의 댓글이 있습니다.

• 
  mongsiry014

  nowCapacity 이 음수일 때 0이 리턴되는게 문제 생기지 않을까요?

  위 코드를 실행해서 입력을 다음과 같이 주었더니 출력에 문제가 생겼네요.
  입력 :
  1 2 10
  one 1 1
  two 100 100

  출력 :
  100 1
  two

  가방 부피가 10이니 two 아이템은 절대로 담을 수 없어야 하는데
  two를 출력하고 있어요.

  nowCapacity가 음수 일때는 0을 리턴하는게 아니라
  마이너스 무한대값을 리턴하게 하든지 if문을 통해 재귀함수 호출 전 nowCapacity가 음수인 경우는 없도록하는지 바꿔야 할 것 같아요.

  
  10년 전 link

• 
  riceluxs1t

  제껀 위의 input에도 올바르게 작동하는데 ㅋ.ㅋ.. 제껏도 한번봐주시면 감사하겟습니다

  
  10년 전 link

• 
  riceluxs1t

  https://algospot.com/forum/read/2688/ 글입니다.

  
  10년 전 link

• 
  kdh9520

  import java.util.*;

  class Main {
  private static int[] weightArr, priorityArr;
  private static int numOfItem, maxCapacity;
  private static int[][] cache;
  private static String[] itemNameArr;

  public static void main(String[] args) {
      Scanner keyboard = new Scanner(System.in);
      int testcaseN = keyboard.nextInt();
  
      String[] resultArr = new String[testcaseN];
  
      for (int i = 0; i < testcaseN; i++) {
          resultArr[i] = "";
          numOfItem = keyboard.nextInt();
  
          maxCapacity = keyboard.nextInt();
  
          Stack<String> print = new Stack<>();
  
          // [a][b]는 a개아이템을 쓸 수 있고 현재 가방용량이 b일 때 최대 중요도값
          cache = new int[numOfItem + 1][maxCapacity + 1];
  
          // 각각 1~numofitem인덱스 까지의 정보를 담음
          itemNameArr = new String[numOfItem + 1];
          weightArr = new int[numOfItem + 1];
          priorityArr = new int[numOfItem + 1];
  
          for (int j = 1; j < numOfItem + 1; j++) {
              itemNameArr[j] = keyboard.next();
              weightArr[j] = keyboard.nextInt();
              priorityArr[j] = keyboard.nextInt();
          }
  
          int maxPriority = findMaxPriority(numOfItem, maxCapacity);
  
  
          // 백트래킹으로 리스트를 뽑음
          // 바로위에거랑 똑같으면 현재 것 안넣은것
          int k = numOfItem;
          int l = maxCapacity;
          while (k > 0 && l > 0) {
              if (cache[k][l] != cache[k - 1][l]) {// 현재것 넣은 것
                  print.add(itemNameArr[k]);
                  l -= weightArr[k];
              }
              k--;
          }
  
          resultArr[i] = resultArr[i]
                  .concat(maxPriority + " " + print.size());
  
          while (print.size() > 0) {
              resultArr[i] = resultArr[i].concat("\n" + print.pop());
          }
      }
      for (int i = 0; i < testcaseN; i++) {
          System.out.println(resultArr[i]);
      }
  
  }
  
  // usableIndex는 1~itemNum
  // mowCapacity는 1~maxCap
  private static int findMaxPriority(int usableIndex, int nowCapacity) {
  
      int ret = 0;
  
      // 잘못된 입력값에 대한 처리
      if (usableIndex <= 0 || nowCapacity <= 0 || usableIndex > numOfItem
              || nowCapacity > maxCapacity)
          return ret;
  
      if (cache[usableIndex][nowCapacity] != 0)
          return cache[usableIndex][nowCapacity];
  
      if (usableIndex == 1) {// BaseCase는 현재 쓸 수 있는 갯수가 1일 경우! - 1일 경우는 윗줄이
                              // 무조건 0이므로 아래 코드로 비교가 안됨!
          if (nowCapacity >= weightArr[usableIndex])
              return cache[usableIndex][nowCapacity] = priorityArr[usableIndex];
          else
              return cache[usableIndex][nowCapacity] = 0;
      }
  
      // 현재것을 넣은 값과 안넣은 값을 비교해 줌
      int includeNowItems = findMaxPriority(usableIndex - 1, nowCapacity
              - weightArr[usableIndex])
              + priorityArr[usableIndex];// 현재 넣은값
  
      int decludeNowItems = findMaxPriority(usableIndex - 1, nowCapacity); // 현재
                                                                              // 안넣은값
      if (weightArr[usableIndex] > maxCapacity) { //용량이 맥스보다 크면 - 즉 와이축으로 표의 범위를 벗어나면 안넣은값으로함
          ret = decludeNowItems;
          return cache[usableIndex][nowCapacity] = ret;
      }
  
      if (includeNowItems >= decludeNowItems) {
          ret = includeNowItems;
          return cache[usableIndex][nowCapacity] = ret;
      } else {
          ret = decludeNowItems;
          return cache[usableIndex][nowCapacity] = ret;
      }
  }

  }

  고친코드입니다.

  
  10년 전 link

• 
  mongsiry014

  고친 코드의 잘못된 출력이 되는 경우입니다.
  입력 값:
  1
  3 100
  one 50 100
  two 60 1000
  three 50 100
  출력 값:
  1100 2
  two
  three

  two 와 three의 부피 합은 110이여서 가방 부피보다 큰데도 두개를 포함하고 있어요.
  //용량이 맥스보다 크면 - 즉 와이축으로 표의 범위를 벗어나면 안넣은값으로함 <--- 이 부분을
  //용량이 nowCapacity보다 크면..... <--- 이렇게 바꾸는게 어떨까요?
  현재 남은 용량보다 큰 물건을 담을수는 없으니까요

  
  10년 전 link

• 
  mongsiry014

  riceluxs1t님 글에도 댓글달았어용

  
  10년 전 link

• 
  teufel1231

  댓글에 나와있는 모든, input 에도 제대로 출력되는데, 제출 시 FAIL 되는 이유를 도저히 모르겠습니다. comment 좀 부탁 드리겠습니다~

  무게순으로 역순으로 소팅 한 후, 재귀함수통해서 불건 조합을 찾았습니다.
  int main(){

  int T=0; 
  int Answer=0;
  
  cin >> T;
  
  for(int test_case =0; test_case<T;test_case++){
  
  
  
  
      // input 
      cin >> g_N;
      cin >> g_W; 
  
      if( (g_N <=0) || (g_N > 100) ||
          (g_W <=0 ) || (g_W > 1000))
      {
  
          cout<<0<<" "<<0<<endl;
          continue;
      }
  
      for(int i=0;i<g_N;i++){
          buf[i].init();
          cin>>buf[i]._name;
          cin>>buf[i]._weight;
          cin>>buf[i]._favor;
  
          if( buf[i]._weight > 1000 || buf[i]._weight <0  || 
              buf[i]._favor > 1000 || buf[i]._favor < 0)
          {
              cout<<0<<" "<<0<<endl;
              continue;
          }
      }
  
  
      // runModule 
      Answer = runModule();
  
  
      // AnSwer 
      cout<<answer_Sum << " " << answer_Cnt<<"\n";
      for(int i=0;i<101;i++){
          if(answerBuf[i] > 0)
              cout<<buf[i]._name<<"\n";
      }
      cout<<endl;
  }
  
  
  
  return 0;

  }

  int runModule()
  {
  int nRet=0;
  memset(answerBuf,0,sizeof(char)*101);

  // 무게 역순 정렬 
  sortBuf();
  
  // 물건 조합 하기
  int SavedWeight=0;
  int SavedCnt=0;
  int requestWeight=g_W;
  
  packStuff(answerBuf,requestWeight,SavedWeight,SavedCnt);
  
  answer_Sum = SavedWeight;
  answer_Cnt = SavedCnt;
  
  return nRet;

  }

  int packStuff(char*queue,int MaxW,int &accuW,int& accuCnt)
  {
  int nRet=1;

  if(MaxW <=0)
      return 0;
  
  int fndPos=-1;
  int loop=0;
  while(loop < g_N){
      if((queue[loop] ==0 )&& (   buf[loop]._weight <= MaxW)){
          fndPos=loop;
          break;
      }
      loop++;
  }
  
  
  if(fndPos == -1){
      return 0;
  }
  
  int nMaxPos=0,nMaxValue=0;
  while(loop < g_N){
  
      if( (queue[loop] == 0)  && 
          (buf[loop]._favor > nMaxValue)){
              nMaxValue=buf[loop]._favor ;
              nMaxPos = loop;
      }
      loop++;
  }
  
  queue[nMaxPos]=1;
  MaxW -= buf[nMaxPos]._weight;
  accuW+=buf[nMaxPos]._favor;
  accuCnt++;
  
  nRet += packStuff(queue,MaxW,accuW,accuCnt);
  
  return nRet;

  }

  bool sortBuf()
  {
  int nCnt=g_N;
  int i=0,j=0;
  InputData temp;

  for(i=0;i<nCnt;i++){
      for(j=0;j<nCnt-1;j++){
          if( buf[j]._weight < buf[j+1]._weight ){
              temp.init();
              temp.copy(buf[j]);
              buf[j].copy(buf[j+1]);
              buf[j+1].copy(temp);
          }
      }// end j
  }// end i
  
  
  return true;

  }

  부탁드립니다~~

  
  9년 전 link

• 
  Kureyo

  문제에 대한 질문은 댓글이 아닌 질문게시판을 이용해주세요

  
  9년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.