CodeInvicta: CINVIT03: EDITORIAL
Problem
Knapsack
Problem:
Chef is having a Knapsack which contains Mangoes of different weight. Let’s take an array knap[] of size N which contains {knap[0], knap[1], ……………, knap[n−1]}, where knap[i] denotes the weight of a mango ii. Also, he wants to sell all these mangoes by packing all those in a different Carry bag. The number of mangoes each Carry bag can hold is given in cb[] array of size M. cb[i] denotes the number of mangoes can a particular Carry bag carry. So, Chef will keep exactly cb[i] the number of mangoes in this Carry_bag.
NoteNote that {cb[0]+ cb[1]+ …… +cb[m−1] = N}
At the same time, he wants to fill the Carry bag in a different manner. He wants to fill all the Carry bag in such a way that the total sum of minimum and maximum weight of mangoes present in every Carry bag after packing is maximum. Chef wants you to find the required sum.
Input
The first line contains two integers Nand M (1≤N≤105;1≤M≤N) — the size of knap[] array and the size of cb[] array.
The second line contains N integers a1, a2, …, an($1 ≤ ai ≤ 10^5) — the weight of mangoes present in knapsack.
The third line contains MM integers c1, c2, …, cM ($1 ≤ ci ≤ n) — number of mangoes Chef will keep in each Carry bag.
Output
Print a single integer — the maximum sum.
Sample Input
4 2
1 10 6 15
1 3
Sample Output
41
Explanation
The chef should keep the greatest weight in the first Carry bag {15}. So, 15 is the minimum and 15 is the maximum & remaining unit of mangoes kept in the second Carry bag {1,6,10}. So 1 is the minimum and 10 is the maximum. So, the total sum = 15+15+1+10 = 41 which is the maximum.
Solution
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int arr[]=new int[n+1]; //We are taking knapsack array as arr[]
int wt[]=new int[m+1]; // Here we are taking cb[] array as wt[]
//taking user input
for(int i=1;i<=n;i++){
arr[i]=sc.nextInt();
}
for(int i=1;i<=m;i++){
wt[i]=sc.nextInt();
}
//Here we have sorted both the Array
Arrays.sort(arr,1,n+1);
Arrays.sort(wt,1,m+1);
/*Here Result is initialized...We have taken 2 pointers i & j, where i is denoting 1 and j is denoting n initially.
p is the pointer which denoting in wt[]...First we will make sure to fill the requirements of carry_bag having capacity of 1
mango..so while p is less than equals to m because m is maximum number of quantity... wt[p] are which basically represent the requirements of carry_bag.
if requirement is 1 then we would add in the result (res).. In arr[j] , j represents maximum weight of mango available..
we have to keep maximum in all carry bag which quantity is 1....so we will multiply by 2 in result...*/
int res = 0;
int i = 1;
int j = n;
int p = 1;
while(p <= m && wt[p] == 1){
res += 2 * arr[j] ;
j-- ;
p++;
}
//Now we will starting from m because first we have to fill max carry bag
for(int q=m;q>=p;q--)
{
res += arr[j] + arr[i];
j-- ; i++ ; wt[q] -= 2;
while(wt[q] > 0){
i++ ; wt[q]--;
}
}
System.out.println(res);
}
}