C++에서 배낭 문제 알고리즘을 사용하는 방법

C++에서 배낭 문제 알고리즘을 사용하는 방법

배낭 문제는 컴퓨터 알고리즘의 고전적인 문제 중 하나입니다. 배낭 용량에 따라 배낭에 넣을 항목을 선택하는 방법이 포함됩니다. 아이템의 가치가 극대화됩니다. 이 기사에서는 배낭 문제를 해결하기 위해 C++에서 동적 프로그래밍 알고리즘을 사용하는 방법을 자세히 소개하고 구체적인 코드 예제를 제공합니다.

먼저 배낭 문제의 입력과 출력을 정의해야 합니다. 입력에는 아이템의 무게 배열 wt[], 아이템의 값 배열 val[], 배낭의 용량 W가 포함됩니다. 결과는 가치를 극대화하기 위해 배낭에 넣을 품목을 선택하는 것입니다.

int knapSack(int W, int wt[], int val[], int n) {
   // 动态规划表格
   int dp[n+1][W+1];
  
   // 填充动态规划表格
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= W; j++) {
         if (i == 0 || j == 0)
            dp[i][j] = 0; // 边界条件
         else if (wt[i - 1] <= j)
            dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
         else
            dp[i][j] = dp[i - 1][j];
      }
   }
  
   return dp[n][W]; // 返回最大价值
}

위 코드에서는 2차원 배열 dp[][]를 사용하여 동적 프로그래밍의 상태 전이 테이블을 나타냅니다. 여기서 dpi는 첫 번째 i 항목의 선택과 배낭 용량을 나타냅니다. j 최대 총 가치입니다. 구체적인 알고리즘은 다음과 같이 구현됩니다.

1. 2차원 배열 dp[][]의 첫 번째 행과 열을 0으로 초기화하여 선택할 항목이 없거나 용량이 0일 때 최대 총 값을 나타냅니다.

2. 1행과 1열부터 시작하여 각 dpi를 계산합니다.

   • 현재 항목의 무게[i-1]가 배낭 용량 j보다 작거나 같으면 다음을 선택할 수 있습니다. 아이템을 넣을지 말지 선택하세요. 해당 상황에서 가장 큰 합계 값을 선택하세요.
   • 현재 아이템의 무게가 배낭 용량 j보다 크면 현재 아이템을 넣을 수 없습니다. in, 총 값은 이전 상태, 즉 dpi-1과 동일합니다.
3. 최종적으로 처음 n개 항목 중 선택 시 최대 총 값을 나타내는 dpn을 반환하며 배낭 용량은 W입니다.

다음은 배낭 문제 알고리즘을 사용한 샘플 코드입니다.

#include 
using namespace std;

int knapSack(int W, int wt[], int val[], int n) {
   // 动态规划表格
   int dp[n+1][W+1];
  
   // 填充动态规划表格
   for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= W; j++) {
         if (i == 0 || j == 0)
            dp[i][j] = 0; // 边界条件
         else if (wt[i - 1] <= j)
            dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j]);
         else
            dp[i][j] = dp[i - 1][j];
      }
   }
  
   return dp[n][W]; // 返回最大价值
}

int main() {
   int val[] = {60, 100, 120};
   int wt[] = {10, 20, 30};
   int W = 50;
   int n = sizeof(val) / sizeof(val[0]);
   cout << "最大总价值为：" << knapSack(W, wt, val, n) << endl;
   return 0;
}

위 코드를 실행하면 출력된 결과의 총합 최대값은 220입니다. 즉, 배낭 용량이 50일 때 사용할 수 있는 최대값은 항목 1과 3의 합계 값을 선택하여 얻습니다.

위의 동적 프로그래밍 방법 외에도 백트래킹 및 탐욕 알고리즘과 같은 다른 방법을 사용하여 배낭 문제를 해결할 수도 있습니다. 위 내용은 C++에서 배낭 문제 알고리즘을 사용하는 방법에 대한 자세한 소개입니다.

위 내용은 C++에서 배낭 문제 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!