Home > Backend Development > C++ > In C language, translate the following into Chinese: 0-1 knapsack problem

In C language, translate the following into Chinese: 0-1 knapsack problem

WBOY
Release: 2023-09-03 11:17:06
forward
1273 people have browsed it

In C language, translate the following into Chinese: 0-1 knapsack problem

A backpack is a bag. Whereas the knapsack problem involves placing items into bags based on their value. Its goal is to maximize the value within the bag. In a 0-1 backpack, you can choose to put an item in or discard it, there is no concept of putting part of an item into the backpack.

Example problem

Value of items = {20, 25,40}
Weights of items = {25, 20, 30}
Capacity of the bag = 50
Copy after login

Weight distribution

25,20{1,2}
20,30 {2,3}
If we use {1,3} the weight will be above the max allowed value.
For {1,2} : weight= 20+25=45 Value = 20+25 = 45
For {2,3}: weight=20+30=50 Value = 25+40=65
Copy after login

The maximum value is 65, so we put items 2 and 3 into the backpack.

0-1 Knapsack Problem Program

#include<stdio.h>
int max(int a, int b) {
   if(a>b){
      return a;
   } else {
      return b;
   }
}
int knapsack(int W, int wt[], int val[], int n) {
   int i, w;
   int knap[n+1][W+1];
   for (i = 0; i <= n; i++) {
      for (w = 0; w <= W; w++) {
         if (i==0 || w==0)
            knap[i][w] = 0;
         else if (wt[i-1] <= w)
            knap[i][w] = max(val[i-1] + knap[i-1][w-wt[i-1]], knap[i-1][w]);
         else
            knap[i][w] = knap[i-1][w];
      }
   }
   return knap[n][W];
}
int main() {
   int val[] = {20, 25, 40};
   int wt[] = {25, 20, 30};
   int W = 50;
   int n = sizeof(val)/sizeof(val[0]);
   printf("The solution is : %d", knapsack(W, wt, val, n));
   return 0;
}
Copy after login

Output

The solution is : 65
Copy after login

The above is the detailed content of In C language, translate the following into Chinese: 0-1 knapsack problem. For more information, please follow other related articles on the PHP Chinese website!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template