Surplus Value Backpack
- Tag: #linkedlist
There is a backpack with a capacity of c.
There are n Class A items, the volume of the i th Class A item is a[i], and the value of the item is the remaining capacity of the backpack after loading the item * k1.
There are m Class B items, the volume of the i th Class B item is b[i], and the value of the item is the remaining capacity of the backpack after loading the item * k2.
Find the maximum value can be obtained.
- 1 <= k1, k2, c, a[i], b[i] <= 10^7
- 1 <= n, m <= 1000
Given k1 = 3,k2 = 2,c = 7,n = 2,m = 3,a = [4,3],b = [1,3,2],return 23. Explanation: 2 * (7-1)+2*(6-2) + 3 * (4-3) = 23
Given k1 = 1,k2 = 2,c = 5,n = 1,m = 1,a = ,b = ,return 10. Explanation: 2 * (5-1)+1*(4-2) = 10
Credits To: lintcode.com
Leave me comments, if you have better ways to solve.
## Blog link: https://code.dennyzhang.com/surplus-value-backpack class Solution: """ @param k1: The coefficient of A @param k2: The coefficient of B @param c: The volume of backpack @param n: The amount of A @param m: The amount of B @param a: The volume of A @param b: The volume of B @return: Return the max value you can get """ def getMaxValue(self, k1, k2, c, n, m, a, b): # Write your code here