//You want to send your friend a package with different things.

//Each thing you put inside the package has such parameters as index number, weight and cost.

//The package has a weight limit.

//Your goal is to determine which things to put into the package so that the total weight is less than

//or equal to the package limit and the total cost is as large as possible.

//You would prefer to send a package which weights less in case there is more than one package with the same price.

//INPUT SAMPLE:

//Your program should accept as its first argument a path to a filename.

//The input file contains several lines. Each line is one test case.

//Each line contains the weight that the package can take (before the colon) and the list of things you need to choose.

//Each thing is enclosed in parentheses where the 1st number is a thing's index number, the 2nd is its weight and the 3rd is its cost.

//E.g.

//81 : (1,53.38,$45) (2,88.62,$98) (3,78.48,$3) (4,72.30,$76) (5,30.18,$9) (6,46.34,$48)

//8 : (1,15.3,$34)

//75 : (1,85.31,$29) (2,14.55,$74) (3,3.98,$16) (4,26.24,$55) (5,63.69,$52) (6,76.25,$75) (7,60.02,$74) (8,93.18,$35) (9,89.95,$78)

//56 : (1,90.72,$13) (2,33.80,$40) (3,43.15,$10) (4,37.97,$16) (5,46.81,$36) (6,48.77,$79) (7,81.80,$45) (8,19.36,$79) (9,6.76,$64)

//OUTPUT SAMPLE:

//For each set of things that you put into the package provide a list (items’ index numbers are separated by comma). E.g.

//4

//-

//2,7

//8,9

//CONSTRAINTS:

//Max weight that a package can take is ≤ 100

//There might be up to 15 items you need to choose from

//Max weight and cost of an item is ≤ 100

package com.practice;

import java.io.BufferedReader;

import java.io.File;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.IOException;

import java.util.ArrayList;

import java.util.List;

public class PackageProblem{

public static void parserpackages(String[] sub2,List<Package> packages,double maxWeight){

for(int i=0;i<sub2.length;i++)

{

String[] sub3=(sub2[i].substring(1,sub2[i].length()-1)).split(",");

int id=Integer.parseInt(sub3[0]);

double weight=Double.parseDouble(sub3[1]);

double cost=Double.parseDouble(sub3[2].substring(1,sub3[2].length()));

if(weight<=maxWeight)

{

Package condidat=new Package(id,weight,cost);

packages.add(condidat);

}

}

}

static String getOptimumFor(List<Package> packages, int r,int NmaxWeight){

int indexSolution=0;

String returnData ="";

double maxWeight=0;

double maxCost=0;

int[] data=new int[r];

List<Integer> res = new ArrayList<Integer>();

int[] arr=new int[packages.size()];

for(int i=0;i<packages.size();i++)

{

arr[i]=i;

}

getCombination(arr, data, res, 0, 0);

//res contien les combinaison de longeur r

//calcule des somme cost et weight

for(int i=0;i<=res.size()-r;i+=r)

{

double somWeight=0;

double somCost=0;

for(int j=0;j<r;j++)

{

somWeight+=packages.get(res.get(i+j)).getWeight();

somCost+=packages.get(res.get(i+j)).getCost();

}

if(somWeight<=NmaxWeight){

if((somCost>maxCost)||((somCost==maxCost)&&(somWeight<=maxWeight)))

{

indexSolution=i;

maxWeight=somWeight;

maxCost=somCost;

}

}

}

for(int k=indexSolution;k<r+indexSolution;k++)

{

returnData+=res.get(k)+",";

}

return returnData+maxCost+","+maxWeight;

}

static void getCombination(int arr[], int data[],List<Integer> res, int start, int index)

{

if (index == data.length)

{

for (int j=0; j<data.length; j++){

res.add(data[j]);

}

return;

}

for (int i=start; i<arr.length && arr.length-i >= data.length-index; i++)

{

data[index] = arr[i];

getCombination(arr, data,res, i+1, index+1);

}

}

public static void main (String[] args) {

File file = new File("D:/packageproblem.txt");

BufferedReader in = null;

try {

in = new BufferedReader(new FileReader(file));

} catch (FileNotFoundException e) {

e.printStackTrace();

}

String line;

List<Package> packages=new ArrayList<Package>();

try {

while ((line = in.readLine()) != null) {

String s="";

//Parsing line

String[] sub1=line.split(" : ");

int N=Integer.parseInt(sub1[0]);

String[] sub2=sub1[1].split(" ");

if(sub2.length>1)

{

packages.clear();

parserpackages(sub2,packages,N);

double maxCost=0;

double maxWeight=0;

for(int i=1;i<=packages.size();i++)

{

String resultat=getOptimumFor(packages,i,N);

//System.out.println(resultat);

String[] sub4=resultat.split(",");

double cost=Double.parseDouble(sub4[sub4.length-2]);

double weight=Double.parseDouble(sub4[sub4.length-1]);

if(cost==maxCost)

{

if(weight<maxWeight){

maxCost=cost;

maxWeight=weight;

s=resultat;

}

}

if(cost>maxCost)

{

maxCost=cost;

maxWeight=weight;

s=resultat;

}

}

//System.out.println(s);

String[] sub5=s.split(",");

String ss="";

for(int i=0;i<sub5.length-2;i++)

{

ss+=packages.get(Integer.parseInt(sub5[i])).getId()+",";

}

if(ss.equals(""))

System.out.println("-");

else

System.out.println(ss.substring(0,ss.length()-1));

}else

System.out.println("-");

}

} catch (IOException e) {

e.printStackTrace();

}

}

}

class Package {

private int id;

private double weight;

private double cost;

public Package() {

super();

}

public Package(int id, double weight, double cost) {

super();

this.id = id;

this.weight = weight;

this.cost = cost;

}

public int getId() {

return id;

}

public void setId(int id) {

this.id = id;

}

public double getWeight() {

return weight;

}

public void setWeight(double weight) {

this.weight = weight;

}

public double getCost() {

return cost;

}

public void setCost(double cost) {

this.cost = cost;

}

@Override

public String toString() {

return "Package [id=" + id + ", weight=" + weight + ", cost=" + cost

+ "]";

}

}