0-1 배낭 문제를 해결하는 C++ 프로그램

0-1 배낭 문제에서는 각 항목에 가중치와 값이 있는 항목 집합이 제공됩니다. 총 무게가 주어진 제한 이하이고 총 값이 가능한 한 크도록 컬렉션에 포함할 각 항목의 수를 결정해야 합니다.

입력

Value = [10, 20, 30, 40, 60, 70]
Weight=[1, 2, 3, 6, 7, 4]
int w=7

출력

knapsack value is: 100

알고리즘

Begin
   Input: set of items each with a weight and a value
   Set knapsack capacity
   Number of items=sizeof(values) / sizeof(values[0])
   Knapsack(Values (stored in array v), Weights (stored in array w), Number of
   distinct items (n), Knapsack capacity W)
   If (w < 0)
      Return
   If no items left or capacity becomes 0
      Return 0
   Include current item n in knapSack (v[n]) and recurs for
   remaining items (n - 1) with decreased capacity (W - w[n])
   Exclude current item n from knapSack and recurs for
   remaining items (n - 1)
   Return maximum value we get by including or excluding current item
End

예시 코드

#include <iostream>
#include <climits>
using namespace std;
int knapSack(int v[], int w[], int n, int W) {
   if (W < 0)
      return INT_MIN;
   if (n < 0 || W == 0)
      return 0;
   int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
   int ex = knapSack(v, w, n - 1, W);
   return max (in, ex);
}
int main() {
   int v[] = { 10, 20, 30, 40, 60, 70 };
   int w[] = { 1, 2, 3, 6, 7, 4 };
   int W = 7;
   int n = sizeof(v) / sizeof(v[0]);
   cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
   return 0;
}

출력

Knapsack value is 100