Problem
Author: Man Mohan Mishra
Tester: Aditya Sarode
Editorialist: Vaibhav Tulsyan
Difficulty
Medium
Pre-requisites
Dynamic Programming, Knapsack Problem
Problem
Given N liquids each having volume V_i and cost P_i, and K containers with capacity C_i, assign at most one liquid to a container where the volume of the liquid should be less than or equal to the capacity of the container, such that the total volume assigned is maximized and the total cost of the liquids assigned is at most M.
Quick Explanation
Let f(i, j, k) represent the maximum volume of liquid using first i liquids, a total cost j, using some of the containers that can be represented using a bitmask k, where a set bit represents a used container.
f(i, j, k) = max(f(i, j, k), f(i - 1, j, k), f(i - 1, j - P_i , k \oplus 2^y) + V_i), where y represents the positions where the i^{th} liquid can be put and \oplus represents the XOR operation.
Detailed Explanation
The problem is similar to the Knapsack Problem.
Just like in the Knapsack problem a constraint on the total weight of the knapsack exists, in this problem, the constraint exists on the total cost, i.e., M. Hence, we must pick a subset of liquids such that the total cost of the liquids put into the containers is \le M.
The next constraint is that each container can contain one liquid completely or not contain anything. Since the maximum number of containers is 5, we can use a bitmask to represent which containers are used up and which aren’t.
Our goal is to maximize the volume utilized, using a subset of N liquids, at most total cost of M units and a subset of K containers.
For each liquid, there are 2 possibilities:
The liquid is assigned to a container and is part of the optimal solution
The liquid is not used and is not part of the optimal solution
Case 1: The liquid is assigned to a container
There can be several containers in which the liquid can be put and all valid possibilities must be considered. That is, out of the K containers, we must consider the containers which have a capacity greater or equal to the volume of the liquid being assigned.
Let us represent our DP state by f(i, j, k), where i represents the index of the liquid, j represents the total amount of money being used and k represents a bitmask, representing that if the x^{th} container is used, then the x^{th} bit in the bitmask will be set to 1, else 0.
In case 1, since we are using the i^{th} liquid and the x^{th} container, we can reach the current state from all such states in which the x^{th} container is un-used, the number of liquids we have seen uptil now is i - 1 and the total amount of cost used is less than or equal to M - P_i.
Such states can be represented by f(i - 1, j - P_i, k \oplus 2^y).
\oplus : Bitwise-XOR operation
y: Index of the container in which i^{th} liquid is being put, and hence 1 \le y \le K.
Case 2: The liquid is not assigned to any container
The state from which we can reach f(i,j,k) in this case is f(i - 1,j,k).
f(i, j, k) = max(f(i - 1, j, k), f(i - 1, j - P_i , k \oplus 2^y) + V_i) for y: 1 \le y \le K and V_i \le C_y.
The maximum value of f(i, j, k) over all states is the maximum volume that can be put into the containers using total cost M.
Refer Tester’s solution for understanding the implementation of this idea.
Setter’s solution omits storing the index i, and just maximizes f(j, k) in the same way, which uses lesser memory.