Untitled

 avatar
unknown
plain_text
4 years ago
626 B
4
Indexable
#include <bits/stdc++.h>
using namespace std;

int getMaxProfit(vector<int> amount, vector<int> profit, int n, int k) 
{
    vector<int> dp(k + 1, 0);
    for (int i = 1; i < n + 1; i++) 
    {
        for (int w = k; w >= 0; w--) 
        {
            if (amount[i - 1] <= w) 
            {        
                dp[w] = max(dp[w], dp[w - amount[i- 1]] + profit[i - 1]);
            }
        }
    }
    return dp[k];
}

int main()
{
	int n,k;
	cin>>n>>k;

	vector<int> amount(k);
	vector<int> profit(k);

	for(auto &x : amount)cin>>x;

	for(auto &x : profit)cin>>x;

	cout<<getMaxProfit(amount,profit,k,n);

	return 0;
}
Editor is loading...