DynamicProgramming/Knapsack-TopDownDp.cpp at main · manishk-99/DynamicProgramming · GitHub

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
37
38
39
#include<bits/stdc++.h>
using namespace std;

int main() {
    int n = 3;
    int wt[] = { 10, 20, 30 };
    int val[] = { 60, 100, 120 };
    int W = 50;
    int dp[n+1][W+1];
    for(int i=0;i<n+1;i++)
        for(int j=0;j<W+1;j++)
            if(i==0 || j==0)
                dp[i][j] = 0;
    for(int i=1;i<n+1;i++)
        for(int j=1;j<W+1;j++)
            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];
    cout<<dp[n][W]<<endl;


    // for(int i=0;i<n+1;i++)
    // {
    //     for(int j=0;j<W+1;j++)
    //     {
    //         cout<<dp[i][j]<<" ";
    //     }
    //      cout<<endl;
    // }

}


// 220
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
// 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60 60
// 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 60 100 100 100 100 100 100 100 100 100 100 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160 160
// 0 0 0 0 0 0 0 0 0 0 60 60 60 60 60 60 60 60 60 60 100 100 100 100 100 100 100 100 100 100 160 160 160 160 160 160 160 160 160 160 180 180 180 180 180 180 180 180 180 180 220