Resource Allocation Dynamic Programming

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Resource Allocation Dynamic Programming. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

PhonePe wants to distribute a fixed promotional budget across merchants. For each merchant, several campaign options are available, where each option has a spending cost and an expected business value. Select at most one option per merchant and maximize the total expected value without exceeding the budget.

Formal Specification

Implement allocate_campaign_budget(budget, merchant_options), where budget is an integer and merchant_options[i] is a list of [cost, value] pairs for merchant i. The function must return the maximum total value achievable. A merchant may receive no campaign, and unused budget is allowed.

Constraints

0 <= budget <= 10^4
1 <= len(merchant_options) <= 100
Each merchant has at most 20 options
0 <= cost <= budget
0 <= value <= 10^6
Each option is represented as [cost, value]
At most one option may be selected for each merchant

Function Signature

def allocate_campaign_budget(budget, merchant_options):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output