Tom is performing an experiment in which he has to select N products. Each product has two attributes i.e. energy and weight. All the products are either manufactured by Reds Ltd. or Blues Ltd. The products manufactured by Blues Ltd. cannot function alone and need to be selected with some other product of the same company. The products from Reds Ltd., on the other hand, can be selected independently. Tom has to select products such that the total weight of the selected products does not exceed the weight W and the selected products have the maximum total energy value.
Write an algorithm to help Tom find the maximum energy.
Input
The first line of the input consists of two space-separated integers - N and W, representing the number of products to select and the threshold value of the total weight of N selected products, respectively.
The next N lines consist of three space-separated integers - e, m and c, representing the energy, weight and the manufacturing company marked as 0 or 1 (0: Reds Ltd, 1: Blues Ltd.), respectively.
Output
Print an integer representing the maximum energy.
Constraints
1 = N = 103
1 = W = 105
1 = e, m = 105
Example
Input:
4 10
4 5 0
2 3 1
3 3 1
4 2 0
Output:
9
Explanation:
The products (1) and (4) can be taken alone but products (2) and (3) can not be taken alone.
The optimal solution is to choose products (2), (3) and (4) and the maximum possible energy is 9.
Answers
Answer:
Explanation:
//by riddhinilawar
import java.util.*;
public class Prac {
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int w=sc.nextInt();
int arr1[]=new int[n];
int arr2[]=new int[n];
int arr3[]=new int[n];
for(int i=0;i<n;i++)
{
arr1[i]=sc.nextInt();
arr2[i]=sc.nextInt();
arr3[i]=sc.nextInt();
}
sc.close();
int r=0;
int b=0;
int max=0;
for(int i=0;i<n;i++)
{
if(arr3[i]==0)
{
r=r+arr1[i];
if(arr1[i]>max)max=arr1[i];
}
else
{
b=b+arr1[i];
}
}
int b1=b+max;
int res=(r>b1)?r:b1;
if(res<w)System.out.print(res);
}
}
Answer:
#include <stdio.h>
#include<math.h>
int findMaxEnergy(int e[],int m[],int c[],int N,int W)
{
int x=(int)pow(2,N);
int count=0;
int maxenergy=0;
int sumenergy=0,summass=0;
for(int i=1;i<x;i++)
{
sumenergy=0;
summass=0;
count=0;
for(int j=0;j<N;j++)
{
if(((i>>j)&1)==1)
{
sumenergy=sumenergy+e[j];
summass=summass+m[j];
if(c[j]==1)
count++;
}
}
if(sumenergy>maxenergy && summass<=W && count%2==0)
maxenergy=sumenergy;
}
return maxenergy;
}
int main()
{
int N,W;
scanf("%d",&N);
scanf("%d",&W);
int e[N];
int m[N];
int c[N];
for(int i=0;i<N;i++)
{
scanf("%d",&e[i]);
scanf("%d",&m[i]);
scanf("%d",&c[i]);
}
printf("%d",findMaxEnergy(e,m,c,N,W));
}
Explanation:
if n=5,generate all the sets using binary number from 1 to 2(power n ).