동적 기획 해결 01 가방 문제 (java 실현)

01배낭문제와 배낭문제의 차이점은 01배낭이다. 물품의 선택은 두 가지가 있는데 하나는 가지지 않는 것이고 다른 하나는 가지지 않는 것이다. 배낭문제는 물품의 일부분만 찾을 수 있다는 것이다.그래서 01 가방 문제는 욕심 알고리즘으로 해결할 수 없다.

는 dp[i][j]로 i종의 물품을 표시하고 무게는 j로 얻은 가치를 나타낸다.

제i종 물품에 대해 제i종 물품의 무게가 j보다 크면 제i종 물품을 찾을 수 없다는 것을 증명한다. 이때 dp[i][j]=dp[i-1][j]

만약에 제i종의 물품 무게가 j보다 작으면 두 가지 상황이 발생한다. i를 사용하면 물품 가치 dp[i][j]= 앞의 i-1종의 물품을 사용하고 차지하는 무게는 j-i.getweight로 발생하는 가치 + 제i종의 물품의 가치.만약 i를 사용하지 않는다면 가치는 dp[i-1][j]이다.수학 표현식으로 바꾸면 dp[i][j]=Math.max(dp[i-1][j-weight]+value,dp[i-1][j]);

예를 들어 i=5, j=10일 때 dp[5][10]는 얻은 최대 가치를 대표한다.여기까지 우리는 임무의 반을 완성하고 도대체 어떤 물건을 가방에 넣었는지 찾아볼 수 있다. 앞의 표현식에서 알 수 있듯이 dp[i][j]=dp[i-1][j-weight]일 때 i를 위한 물건을 가방에 넣는다. 그래서 우리는 결과부터 되돌아간다. 이런 상황에 부딪히면 물건을 가방에 넣었다는 것을 의미한다. 그리고 물건의 수를 1로 줄이고 무게를 i의 무게로 줄인다. 계속,마지막으로 어떤 아이템을 가방에 넣을지 구할 수 있습니다.6. 참조 코드는 다음과 같다:

package com.bc;

public class Test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
         int allweight=12;  //         
         int num=8;   //  
          bao[] baos=new bao[num+1];
          baos[1]=new bao(2, 13);
          baos[2]=new bao(1, 10);
          baos[3]=new bao(3, 24);
          baos[4]=new bao(2, 15);
          baos[5]=new bao(4, 28);
          baos[6]=new bao(5, 33);
          baos[7]=new bao(3, 20);
          baos[8]=new bao(1, 8);
          int[][] dp=new int[num+1][allweight+1];
          //       
          for(int i=0;i<=num;i++)
          {
              for(int j=0;j<=allweight;j++)
              {
                  if(i==0||j==0)
                  {
                      dp[i][j]=0;

                  }else {
                      if (j1][j];
                    }else {
                        int value=baos[i].getValue();
                        int weight=baos[i].getWeight();
                        dp[i][j]=Math.max(dp[i-1][j-weight]+value,dp[i-1][j]);
                    }
                }

                  System.out.println("dp"+"["+i+"]"+"["+j+"]"+dp[i][j]);
              }
          }


          int m=num;
          int n=allweight;
          int all=dp[m][n];
          //          
           while(all>=0)
           {
               if (m>0&&dp[m][n]==dp[m-1][n]) {
                   m=m-1;

                }else {
                    System.out.println(baos[m]+"    ");
                    m=m-1;
                    if (m==0) {
                        return;
                    }else {
                        n=n-baos[m].getWeight();
                        all=all-baos[m].getWeight();
                    }

                }
           }
    }

}