How to use the knapsack problem algorithm in C++

How to use the knapsack problem algorithm in C

The knapsack problem is one of the classic problems in computer algorithms. It involves how to Choose some items to put in your backpack to maximize the total value of the items. This article will introduce in detail how to use the dynamic programming algorithm in C to solve the knapsack problem, and give specific code examples.

First, we need to define the input and output of the knapsack problem. The input includes the weight array wt[] of the item, the value array val[] of the item, and the capacity W of the backpack. The output is choosing which items to put into the backpack to maximize value. The definition is as follows:

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]; // 返回最大价值
}

In the above code, we use a two-dimensional array dp[][] to represent the state transition table of dynamic programming, where dpi represents the selection of the first i items, and the backpack capacity is j The maximum total value of the case. The specific algorithm is implemented as follows:

1. Initialize the first row and column of the two-dimensional array dp[][] to 0, which means that there are no items to choose from or the maximum total value when the capacity is 0 is 0;

2. Starting from row 1 and column 1, calculate each dpi:

   • If the weight of the current item wt[i-1] is less than or equal to the backpack Capacity j, you can choose to put items in or not, and choose the largest total value in both cases;
   • If the weight of the current item wt[i-1] is greater than the backpack capacity j, it cannot Put in the current item, the total value is equal to the previous state, that is, dpi-1;
3. Finally return dpn, indicating that the first n items are selected and the backpack capacity is W the maximum total value.

The following is a sample code using the knapsack problem algorithm:

#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;
}

Run the above code and the maximum total value of the output result is 220, which means that when the knapsack capacity is 50, The maximum total value you can get by choosing Item 1 and Item 3.

In addition to the above dynamic programming methods, the knapsack problem can also be solved using other methods such as backtracking and greedy algorithms. The above is a detailed introduction on how we use the knapsack problem algorithm in C. I hope it will be helpful to you.

The above is the detailed content of How to use the knapsack problem algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!