-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathknapmemo.cpp
More file actions
36 lines (35 loc) · 827 Bytes
/
knapmemo.cpp
File metadata and controls
36 lines (35 loc) · 827 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;
int tab[11][11];
class knapsack
{
public:
int knap(int wt[], int val[], int w, int n)
{
memset(tab, -1, sizeof(tab));
if (w == 0 || n == 0)
return 0;
if (tab[n][w] != -1)
return tab[n][w];
if (wt[n - 1] <= w)
{
return tab[n][w] = max(val[n - 1] + knap(wt, val, w - wt[n - 1], n - 1), knap(wt, val, w, n - 1));
}
else if (wt[n - 1] > w)
{
return tab[n][w] = knap(wt, val, w, n - 1);
}
return tab[n][w];
}
};
int main()
{
int wt[] = {12, 9, 13, 2, 8, 5};
int val[] = {4, 12, 22, 15, 1, 7};
int n = sizeof(val) / sizeof(val[0]);
int w = 15;
knapsack ob;
cout << ob.knap(wt, val, w, n);
}