-
Notifications
You must be signed in to change notification settings - Fork 18
/
code(Book Shop).cpp
46 lines (34 loc) · 1.1 KB
/
code(Book Shop).cpp
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
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,x;
cin>>n>>x;
vector<int> page(n),price(n);
int a,b;
for(int&i : price)
cin>>i;
for(int&i : page)
cin>>i;
vector<vector<int>> dp(n+1,vector<int>(x+1,0));
for(int i=1;i<=n;i++)
{
for(int j=0;j<=x;j++)
{
//option1 = book number i-1 is not included, hence no pages added.
//option2 = book number i-1 is included, hence pages are added.
//option1 = dp[i-1][j] ...book not included so total price(j) remains same.
//option2 = dp[i-1][j-price[i-1]] + page[i-1]....total price(j) decreased and pages are counted for book i-1.
dp[i][j] = dp[i-1][j];
if(j >= price[i-1])
{
dp[i][j] = max (dp[i][j],dp[i-1][j-price[i-1]] + page[i-1]); //max of both the boxes included in dp[i][j].
}
}
}
cout<< dp[n][x] <<endl;
return 0;
}