Book Shop

You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

Example:

Input:  n = 4, m = 10, w = {4, 8, 5, 3}, v = {5, 12, 8, 1}
Output: 13

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int bookShop(int n, int m, vector<int> &w,
             vector<int> &v)
{

    vector<int> dp(m + 1);
    for (int i = 0; i < n; i++)
    {
        for (int j = m; j >= w[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[m];
}

int main()
{
    int n = 4, m = 10;
    vector<int> w = {4, 8, 5, 3};
    vector<int> v = {5, 12, 8, 1};

    cout << bookShop(n, m, w, v) << "\n";

    return 0;
}