Java에서 배낭 문제를 해결하기 위한 예제 코드

이 글에서는 주로 01과 완전한 배낭이라는 두 종류의 배낭이 포함된 Java 배낭 문제 해결 예제 코드를 소개합니다. 두 배낭의 아이디어와 구현 방법이 각각 설명되어 있어 필요한 참고 가치가 있습니다.

백팩 문제는 주로 주어진 용량의 백팩과 특정 가치와 무게를 지닌 여러 개의 아이템을 선택하여 아이템의 가치를 극대화하는 방법을 의미합니다. 01 백팩과 무제한 백팩으로 나누어집니다. 여기서는 주로 01 백팩에 대해 설명합니다. 즉, 각 항목은 최대 1개까지 배치할 수 있습니다. 무한 백팩은 01 백팩으로 변환 가능합니다.

먼저 알고리즘의 주요 아이디어에 대해 이야기하고 이를 해결하기 위해 동적 프로그래밍을 사용하겠습니다. i번째 항목을 순회할 때마다 w[i]와 v[i]에 따라 해당 항목을 배낭에 넣어야 하는지 여부가 결정됩니다. 즉, 주어진 n개의 물품에 대해 v[i]와 w[i]를 각각 i번째 물품의 가치와 무게라고 하고, C는 배낭의 용량이라고 하자. v[i][j]는 용량이 j인 배낭에 넣을 수 있는 첫 번째 i개 항목의 최대값을 나타냅니다. 그러면 다음과 같은 결과가 나옵니다:

(1), v[i][0]=v[0][j]=0;
(2), v[i][j]=v[i-1; ][j] w[i]>j
(3)일 때, v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+ v[i]} j>=w[i]

알고리즘은 이 세 가지 결론 공식을 기반으로 합니다.

1.01 배낭:

1. 2차원 배열 방법

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[][] f = new int[n+1][m+1]; //f[i][j]表示前i个物品能装入容量为j的背包中的最大价值 
    int[][] path = new int[n+1][m+1]; 
    //初始化第一列和第一行 
    for(int i=0;i<f.length;i++){ 
      f[i][0] = 0; 
    } 
    for(int i=0;i<f[0].length;i++){ 
      f[0][i] = 0; 
    } 
    //通过公式迭代计算 
    for(int i=1;i<f.length;i++){ 
      for(int j=1;j<f[0].length;j++){ 
        if(weight[i-1]>j) 
          f[i][j] = f[i-1][j]; 
        else{ 
          if(f[i-1][j]<f[i-1][j-weight[i-1]]+val[i-1]){ 
            f[i][j] = f[i-1][j-weight[i-1]]+val[i-1]; 
            path[i][j] = 1; 
          }else{ 
            f[i][j] = f[i-1][j]; 
          } 
          //f[i][j] = Math.max(f[i-1][j], f[i-1][j-weight[i-1]]+val[i-1]); 
        } 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      for(int j=0;j<f[0].length;j++){ 
        System.out.print(f[i][j]+" "); 
      } 
      System.out.println(); 
    } 
    int i=f.length-1; 
    int j=f[0].length-1; 
    while(i>0&&j>0){ 
      if(path[i][j] == 1){ 
        System.out.print("第"+i+"个物品装入 "); 
        j -= weight[i-1]; 
      } 
      i--; 
    } 
  } 
}

출력:

0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 4 4 4 4 4 4 4 4 4 4 
0 0 0 4 4 4 4 4 8 8 8 8 8 
0 0 3 4 4 7 7 7 8 8 11 11 11 
0 0 3 4 4 7 7 7 8 9 11 12 12 
0 0 3 4 4 7 7 7 8 10 11 12 12 
第4个物品装入 第3个物品装入 第1个物品装入

위의 방법은 모두 O입니다. (N*V)이면 시간 복잡도는 기본적으로 더 이상 최적화할 수 없지만, 공간 복잡도는 O(V)로 최적화할 수 있습니다.

먼저 위에서 언급한 기본 아이디어를 어떻게 구현하는지 생각해 보세요. 메인 루프 i=1..N이 있어야 하고, 매번 2차원 배열 f[i][0..V의 모든 값이 있어야 합니다. ]가 계산됩니다. 그렇다면 하나의 배열 f[0..V]만 사용하는 경우 i번째 루프가 끝난 후 f[v]가 우리가 정의한 상태 f[i][v]를 나타낸다는 것을 보장할 수 있습니까? f[i][v]는 두 하위 문제 f[i-1][v]와 f[i-1][v-c[i]]에서 재귀적으로 파생됩니다. (즉, f[v]가 i번째 메인 루프에 푸시되면) f[i-1][v] 및 f[i-1][v-c[i]]의 값이 얻어질까? 실제로 이를 위해서는 f[v]를 푸시할 때 f[v-c[i]]가 상태 f를 저장하도록 하기 위해 각 메인 루프에서 v=V..0 순서로 f[v]를 푸시해야 합니다. [i -1][v-c[i]] 값.

의사 코드는 다음과 같습니다.

for i=1..N
  for v=V..0
    f[v]=max{f[v],f[v-c[i]]+w[i]};

문장 f[v]=max{f[v],f[v-c[i]]}는 전달 방정식 f[i][v와 정확히 동일합니다. ] =max{f[i-1][v],f[i-1][v-c[i]]}, 현재 f[v-c[i]]는 원래 f[i-1][와 동일하기 때문입니다. v-c [i]]. v의 순환 순서를 위의 역순에서 순서로 바꾸면 f[i][v]가 되며 f[i][v-c[i]]로부터 추론할 수 있는데 이는 의미와 일치하지 않는다. 그러나 이것은 또 다른 중요한 배낭 문제입니다. P02는 가장 간단한 해결책이므로 1차원 배열만을 사용하여 01 배낭 문제를 해결하는 방법을 배우는 것이 매우 필요합니다.

최적의 해결책을 묻는 배낭 문제에는 실제로 질문하는 방법이 두 가지 있습니다. 일부 질문은 배낭이 정확히 채워졌을 때 최적의 솔루션이 필요한 반면, 다른 질문은 배낭을 반드시 채워야 한다고 요구하지 않습니다. 이 두 가지 질문을 구별하는 한 가지 구현 방법은 초기화 중에 차이를 만드는 것입니다.

백팩을 정확히 채워야 하는 첫 번째 질문인 경우 초기화 중에 0인 f[0]을 제외하고 다른 f[1..V]는 -로 설정되어 최종 f를 보장합니다. [N]은 배낭을 정확히 채워주는 최적의 솔루션입니다.

배낭을 채울 필요는 없지만 가격을 최대한 높이고 싶다면 초기화 중에 f[0..V]를 모두 0으로 설정해야 합니다.

왜요? 이는 이렇게 이해될 수 있습니다. 초기화된 f 배열은 실제로 배낭에 어떤 항목도 넣을 수 없는 합법적인 상태입니다. 배낭이 정확히 채워져야 하는 경우, 용량이 0인 배낭만 값이 0인 아무것도 "정확히 채워질" 수 있습니다. 다른 용량을 가진 배낭에 대한 법적 해결책은 없으며 정의되지 않은 상태입니다. , 그리고 그 값은 모두 -무한이어야 합니다. 배낭을 채울 필요가 없다면 용량에 상관없이 배낭에는 "아무 것도 포장하지 않음"이라는 합법적인 솔루션이 있으므로 이 솔루션의 값은 0이므로 초기 상태 값은 모두 0입니다.

2. 1차원 배열 방식(채울 필요 없음)

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[] f = new int[m+1]; 
    for(int i=0;i<f.length;i++){   //不必装满则初始化为0 
      f[i] = 0; 
    } 
    for(int i=0;i<n;i++){ 
      for(int j=f.length-1;j>=weight[i];j--){ 
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      System.out.print(f[i]+" "); 
    } 
    System.out.println(); 
    System.out.println("最大价值为"+f[f.length-1]); 
  } 
}

output

0 0 3 4 4 7 7 7 8 10 11 12 12 
最大价值为12

3. 1차원 배열 방식(반드시 채워야 함)

rrre 에

출력

public class sf { 
  public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int[] weight = {3,5,2,6,4}; //物品重量 
    int[] val = {4,4,3,5,3}; //物品价值 
    int m = 12; //背包容量 
    int n = val.length; //物品个数 
    int[] f = new int[m+1]; 
    for(int i=1;i<f.length;i++){   //必装满则f[0]=0,f[1...m]都初始化为无穷小 
      f[i] = Integer.MIN_VALUE; 
    } 
    for(int i=0;i<n;i++){ 
      for(int j=f.length-1;j>=weight[i];j--){ 
        f[j] = Math.max(f[j], f[j-weight[i]]+val[i]); 
      } 
    } 
    for(int i=0;i<f.length;i++){ 
      System.out.print(f[i]+" "); 
    } 
    System.out.println(); 
    System.out.println("最大价值为"+f[f.length-1]); 
  } 
}

2. 백팩 완성

N 종류의 아이템과 V 용량의 백팩이 있습니다. 각 아이템은 개수 제한이 없습니다. i번째 항목의 비용은 c[i]이고 값은 w[i]입니다. 해당 품목의 총 비용이 배낭 용량을 초과하지 않고 해당 값의 합이 최대가 되도록 배낭에 포장할 수 있는 품목을 찾으십시오.

하지만 우리에게는 더 나은 O(VN) 알고리즘이 있습니다.

O(VN) 알고리즘

이 알고리즘은 1차원 배열을 사용합니다. 먼저 의사 코드를 살펴보세요.

0 -2147483648 3 4 3 7 6 7 8 10 11 12 11 
最大价值为11

이 의사 코드와 P01의 의사 코드를 찾을 수 있습니다. v의 루프만 있습니다. 순서가 다를 뿐입니다.

for i=1..N
  for v=0..V
    f[v]=max{f[v],f[v-cost]+weight}

출력

25

总结

위 내용은 Java에서 배낭 문제를 해결하기 위한 예제 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!