1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 624 - CD
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=565
*
* @author Christian Posselt
* @author Christian Mitterreiter
* @version 1.0, 18.05.2011
*
* Method: Backtracking
* Status: Accepted
* Time: 1.192
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main
{
/**
* length of the single tracks
*/
public static int[] tracks;

/**
* index to solution tracks (for backtracking)
*/
public static int[] indices;

/**
* solution of a problem
*/
public static int[] best;

/**
* amount of tracks
*/
public static int amount;

/**
* max minutes fit on a CD
*/
public static int minutes_max;

/**
* minutes for backtracking trials
*/
public static int minutes_used;

/**
* best solution found so far
*/
public static int maximum;

/**
* amount of Tracks used for the best solution
*/
public static int usedTracks;

public static void main(String[] args) throws IOException
{

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

do
{
Scanner sc = new Scanner(reader.readLine());

minutes_max = sc.nextInt();
minutes_used = 0;
maximum = 0;
usedTracks = 0;
amount = sc.nextInt();

tracks = new int[amount];
indices = new int[amount];
best = new int[amount];

for(int i=0;i<amount;i++)
tracks[i] = sc.nextInt();

//calculate. Start with the first track and no used track so far
caluclate(1,0);

//print solution
for(int i=0;i<=usedTracks;i++)
System.out.print(best[i] + " ");
System.out.print("sum:" + maximum + "\n");
}
while(reader.ready());

}


/**
* Backtracking for the CD problem
*
* @param index: index of track to test next
* @param level: number of tracks taken
*/
public static void caluclate(int index,int level)
{
//Too many minutes
if(minutes_used > minutes_max) return;

//Cannot use tracks multiple times
if(level == amount) return;

//test solutions
for(int i = index; i<=amount; i ++) {

minutes_used += tracks[i-1];

//keep the current index
indices[level] = i;

//found a better solution
if(maximum < minutes_used && minutes_used <= minutes_max)
{
for(int j = 0 ; j<= level; j ++)
{
int k = indices[j];
//put the better solution into best
best[j] = tracks[k-1];
}
//set new best solution amount
maximum = minutes_used;
usedTracks = level;
}
caluclate(i+1,level+1);

minutes_used -= tracks[i-1];
}

}


}


2.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 624 CD
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=565
*
* @author Burgmair Stefan
* @author YYY
* @version 1.0, 24/05/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.800
*/

public class Main
{
static int lengthOfTape;
static int nmbrOfTracks;
static int[] listOfTracks;
static boolean[] isUsed;

public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
do{
String[] input = reader.readLine().split(" ");
lengthOfTape = Integer.parseInt(input[0]);
nmbrOfTracks = Integer.parseInt(input[1]);
listOfTracks = new int[nmbrOfTracks];

isUsed = new boolean[nmbrOfTracks];

for(int i = 0; i < nmbrOfTracks; i++){
listOfTracks[i] = Integer.parseInt(input[i+2]);
isUsed[i] = false;
}

int max = 0;
for (int i = 0; i < listOfTracks.length; i++){
max = max + listOfTracks[i];
}
if(max < lengthOfTape){
for (int i = 0; i < listOfTracks.length; i++){
System.out.print(listOfTracks[i] + " ");
}
System.out.println("sum:" + max);
}
else{
for (int i = lengthOfTape; i > 1; i--)
if(findSolution(0, i, "", i))
break;
}

}while (reader.ready());
}

public static boolean findSolution(int pointer, int remainder, String output, int lengthOfSolution){
if(remainder == 0){
System.out.println(output + "sum:" + lengthOfSolution);
//solutionfound
return true;
}
for(int i = pointer; i < nmbrOfTracks; i++){
if(isUsed[i] == false && remainder-listOfTracks[i] >= 0){
isUsed[i] = true;
if(findSolution(i, remainder-listOfTracks[i], output + listOfTracks[i] + " ", lengthOfSolution))
return true;
isUsed[i] = false;
}
}
return false;
}

public static void printArray(boolean [] arr){
for (int i = 0; i < arr.length; i++)
{
if(arr[i])
System.out.print("t ");
else
System.out.print("f ");

}
System.out.println();
}
}


3.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 624 - CD
* Link: http://w3-o.cs.hm.edu/~logofatu/FWPACM/SS11/contestSimulation18_05.pdf
*
* @author Bastian Hoecker
* @author Philipp Hauck Thalheim
* @version 1.0, 20/05/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.604
*/

public class Main {

static boolean[] check;
static int solSum = 0;
static int trueCount;

static boolean backTrack(int ind, int tapeL, int[] trackL) {
//Falls die Tapelänge == 0 ist, gibt es keine Lösung
if(tapeL == 0) {
return true;
}
//Abbruch wenn das Ende des Arrays erreicht ist und alle Tracks mit true geflaggt wurden
if(trackL.length == ind && trueCount == trackL.length){
return true;
}

//Abbruch wenn das Ende des Arrays erreicht ist
if(ind == trackL.length) {
return false;
}



//Wenn die Tracklänge <= der tapeLänge ist, wird weitergemacht
if(tapeL >= trackL[ind]) {
//Flag wird gesetzt, dass die Zahl mit dem Index ind in die SUmme einbezogen wurd
check[ind] = true;
trueCount++;
//tapeLänge wird um die Länge des Tracks verkürzt
tapeL -= trackL[ind];

if(backTrack(ind+1, tapeL, trackL)){
return true;
}

//tapeLänge wird wieder hochgezählt, trueCount-- und die Flag wieder auf false gesetzt
tapeL += trackL[ind];
check[ind] = false;
trueCount--;
}

if(backTrack(ind+1, tapeL, trackL)){
return true;
}
return false;
}

//Aufruf und Ausgabe von backTrack
static boolean sum(int[] tL, int tapeL) {

check = new boolean[tL.length];
if(backTrack(0, tapeL, tL)) {
for(int i = 0; i < tL.length; ++i) {
if(check[i]){
solSum += tL[i];
System.out.print(tL[i] + " ");
}
}
System.out.println("" + "sum:"+solSum);
return true;
//Falls keine Lösung gefunden wurde, wird die tapeLänge um 1 runtergesetzt
}else if(!backTrack(0, tapeL, tL) && trueCount == 0){
return false;
}

return true;

}



/**
* @param args
*/
public static void main(String[] args) throws IOException{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int tapeLength;
int trackCount;
int[] trackLength;

while(br.ready()){
st = new StringTokenizer(br.readLine());
tapeLength = Integer.parseInt(st.nextToken());
trackCount = Integer.parseInt(st.nextToken());
trackLength = new int[trackCount];

for(int i = 0; i < trackCount; i++){
trackLength[i] = Integer.parseInt(st.nextToken());
}

boolean checkTwo = !sum(trackLength, tapeLength);

while (checkTwo){
check = null;
solSum = 0;
trueCount = 0;
tapeLength--;
checkTwo = !sum(trackLength, tapeLength);
}

check = null;
solSum = 0;
trueCount = 0;



}


}

}

4.

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 624 CD
* Link:
http://w3-o.cs.hm.edu/~logofatu/FWPACM/SS11/contestSimulation18_05.pdf
*
* @author Rolf Schirm
* @version 1.0, 05/18/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.516
*/
public class Main {

public static void main(String... args) throws Exception {
final BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));

String line;
while((line = reader.readLine()) != null) {
final String[] split = line.split(" ");

final int maxLength = Integer.parseInt(split[0]);
final int trackCount = split.length - 2;
final int[] tracks = new int[trackCount];

for(int i = 2; i < split.length; i++) {
tracks[i-2] = Integer.parseInt(split[i]);
}

boolean stop = false;
final int maxCombinations = 1 << trackCount;
int resultCombination = 0;
int bestLength = 0;
for(int combination = 1; combination < maxCombinations && !stop;
combination++) {
int currentLength = 0;
for(int i = 0; i < trackCount; i++) {
if((combination & (1 << i)) != 0) {
currentLength = currentLength + tracks[i];

if(currentLength > maxLength) {
break;
}
}
}
if(currentLength == maxLength) {
resultCombination = combination;
bestLength = maxLength;
stop = true;
} else if(currentLength < maxLength && currentLength > bestLength) {
resultCombination = combination;
bestLength = currentLength;
}
}

for(int i = 0; i < trackCount; i++) {
if((resultCombination & (1 << i)) != 0) {
System.out.print(tracks[i] + " ");
}
}
System.out.println("sum:" + bestLength);
}
}
}




----------------------------------



1.

/*
* ACM Contest training
* Problem: 624 - CD
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=565
*
* @author Patrick Bedat, Philippe Brousse, Christoph Goettschkes
* @version 1.0, 11/14/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.276
*/

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.util.*;

class Main
{

static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static List<Integer> bestSubset;
static int globalMax;

public static void main(String[] agrs) throws IOException
{
do
{
bestSubset = new ArrayList<Integer>();
globalMax = Integer.MAX_VALUE;
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

int n = Integer.parseInt(tokenizer.nextToken());
int tracks = Integer.parseInt(tokenizer.nextToken());

List<Integer> tracksArray = new ArrayList<Integer>();
for (int i = 0; i < tracks; i++)
tracksArray.add(Integer.parseInt(tokenizer.nextToken()));

List<Integer> sorted = new ArrayList<Integer>(tracksArray);
Collections.sort(sorted);
Collections.reverse(sorted);

int s = 0;
for (int i : tracksArray)
s += i;

if (s < n)
{
globalMax = n - s;
bestSubset = tracksArray;
}
else
test(n, tracksArray, s, new ArrayList<Integer>());

StringBuilder out = new StringBuilder();
for (int i : bestSubset)
out.append(i + " ");
out.append("sum:" + (n - globalMax));
System.out.println(out);

}
while (reader.ready());
}

static boolean test(int length, List<Integer> values, int possibleAdd, List<Integer> current)
{
if (length < 0)
return false;

if (length == 0)
{
globalMax = 0;
bestSubset = current;
return true;
}

if (length - possibleAdd > globalMax)
return false;

if (length < globalMax)
{
globalMax = length;
bestSubset = new ArrayList<Integer>(current);
}
List<Integer> t = new ArrayList<Integer>(values);
for (int i = 0; i < values.size(); i++)
{
current.add(values.get(i));
t.remove(0);
if (test(length - values.get(i), t, possibleAdd - values.get(i), current))
return true;
current.remove(current.size() - 1);
}

return false;
}
}