You are given an integer array Inventories representing the ribbon inventories, where Inventories[i] represents the length of the ith ribbon, and an array of orders.
Each order in orders is an array of integers, representing the ribbons needed with certain lengths for that order. For example, if order = [1,2], then that means this order need a ribbon with length 1 and a ribbon with length 2.
You may cut any of the ribbons in the inventory into any number of segments of positive integer lengths, or perform no cuts at all.
However, you cannot combine two ribbons in the inventory to form a longer ribbon and fullfil an order. Each segment/ribbon in the inventory cannot be reused. The question is, what is the maximum number of orders that can be fulfilled?
Example 1:
Input: Inventories = [1,8,7], orders = [[1, 2], [4, 3, 6]]
Output: 2
Explanation:
First cut inventories[1] into [2,6], then the inventory becomes [1, 7, 2, 6]. Use inventories[0] and inventories[2] for the first order. The rest of the inventories are [7,6], then cut the ribbon with the length of 7 into 4 and 3 to fulfill the second order. So in total 2 orders are fulfilled.
Example 2:
Input: Inventories = [1,2,3], orders = [[3, 3], [4]]
Output: 0
Explanation:
None of the orders can be fulfilled. Notice we cannot combine inventories[0] and inventories[1] for orders[0].
Example 3:
Input: Inventories = [3], orders = [[2]]
Output: 1
Explanation:
Cut the ribbon into 2 and 1, and use the first segment for that order.
I have been breaking my head over this, I thought of some greedy approaches, sorting orders by the max ribbon required by each item and processing it. Eg: [[4,3,6], [1,2]] becomes [[1,2],[4,3,6]]. But this fails when order max is less but the number of items in the order is huge.
Does anyone have any approach ?
Any constraint?
Interview problems don't have constraints, you have to optimize it, but you have a polynomial soln ?
Nvm, wrong approach
You mean, you'll have 2^n combinations, in each combination you will see if the corresponding bit mask is satisfied ? But how would you check it ? I mean which inventory item will you map to which order item ?
A corner case: Inventory : [4,6], Order [ [ 3, 3, 4 ] ] , ans is 1.
If you have a list of ribbons lets say x[] and want to satisfy a single list of order, you have to use bitmask dp, accroding to me. Like the checking part. Let dp[i][j] denote if upto ith ribbon can staisfy mask j [Here I am talking of a single list not multiple]. Then transition are
finally answer (true or false) lies in dp[n-1][(1<<sz)-1]; This you can do for all mask of the order list. But I know its slow but will work.
it is a multi knapsack DP, just change the classic 0/1 knapsack for multiple bags.
Why the hell is this downvoted, you can ask,if you guys don't understand or found this wrong.
Anyways I will explain in details so basically your dp states will be total number of bags , now so your states dp would look something like
dp[capacity 1][capacity 2][capacity 3]...[capacity n]
This would be not feasible to implement unless you linearize the dp container.
Now as we do in general knapsack we have to chose a combination that in which container would we put the element , so net complexity will become $$$ O(product (capacity) * product (elements))$$$
This is pseudo polynomial solution .
Of course we could also use exponential solution and memoise it, this would be better in interview both for implementation and ease of explanation.
How do you choose which ordered ribbon is taken from which inventory ribbon?
If inventory = [5, 5] and orders = [[1,1],[4,4]], the only way to fill this is take 0th order from both inventory ribbon and 1st order again from both inventory ribbon. If we try to take 0th order from 1st ribbon only, we can't satisfy 1st order.
How are your transitions for the dp states?? By "bags" you mean inventory ribbons, right?
It does not matter actually because let's say when you take 1 1 from 5 5 so new state will be 4 4 but if you take from only one bag it will be 3 5 , so both the cases are handled as we do in knapsack.
For implementation My transition would be in incremental order for iterative version for(item in listitems)
for(0 to capacity_1 ).....for(0 to capacity_n)
transition or update from prevdp to newdp
It's just modification of 0/1 knapsack basically.
Also while doing transition we are assuming that currently product1 in item is used for bag1 and then again a for loop but update will only happen when we are at the last for loop when we used all the product in item , now as we updating new dp from previous dp it will handle both the case
Also i have to maintain one stack to update past product states as i am doing this iteratively so i also have to update the branxh it was coming from hence i said recursion would be much better here to update. I am not sure if i am explaining this properly but let me know
The simplest (and highest time complexity solution) I can think of is..
We can maybe optimize it a little more by pruning cases where some order is fulfilled partially. But I can't think of any other optimized approach.
You can memoise the states and then your solution is same as i explained , rec(i+1,0) rec(i,j+1) is same as implementing multiple for loops
Yeah, I realized that after reading your reply.
Hello.
I think there isn't any exact algorithm in polynomial-time because the partition problem can be reduced to this.
Suppose there is an exact algorithm for our problem in polynomial-time and we want to know if the array $$$a_1, a_2, \dots, a_n$$$ can be partitioned into two subsets with equal sums or not? We can simply check that with these inputs:
Inventories = $$$[\frac{\sum_{i=1}^n a_i}{2}, \frac{\sum_{i=1}^n a_i}{2}]$$$
orders = $$$[[a_1], [a_2], \dots, [a_n]]$$$
We know there isn't any exact algorithm in polynomial-time for the Partition problem, So there isn't any polynomial-time algorithm for our problem.
I think this problem is similar to the knapsack or partition problem.
Yes you can Simply see the case of one bag and one product in each item , then it's classic knapsack with maximum selection of items given the bag capacity
Edit : wait above case i mentioned, even tho it can be solved using knapsack but it is not needed.just smallest weight items selected greedily to get maximum quantity would work, we can prove using exchange arguments that selecting smaller would be better.