UVA – 624 – CD

Problem Link : UVA – 624 – CD

  • Power Set:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main() {
	int N, cd_length, track[25];
	while (scanf("%d %d", &cd_length, &N) != EOF && cd_length && N) {
		for (int i = 0; i < N; i++)
			scanf("%d", track + i);
		int optimum_mask = 0, optimum_sum = 0;
		for (int mask = 0, sum = 0; mask < (1 << N); sum = 0, mask++) {
			for (int i = 0; i < N; i++)
				sum += ((1 << i) & mask) ? track[i] : 0;
			if (sum > optimum_sum && sum <= cd_length)
				optimum_sum = sum, optimum_mask = mask;
		}
		for (int i = 0; i<N; i++)
			if((1<<i) & optimum_mask)
			printf("%d ", track[i]);

		printf("sum:%d\n", optimum_sum);
	}
	return 0;
}
  • Recursion:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int track[25], cd[25], optimum_cd[25];
int optimum_top, top, N, cd_length, minimum_space, sum;

void max_length(int minutes, int index) {
	if (index == N || minutes - track[index] < 0) {
		if (minutes < minimum_space) {
			minimum_space = minutes, optimum_top = top;
			for (int i = 0; i < top; i++)
				optimum_cd[i] = cd[i];
		}
	} else {
		cd[top++] = track[index];
		for (int i = index + 1; i <= N; i++)
			max_length(minutes - track[index], i);
		top--;
	}
}

int main() {

	while (scanf("%d %d", &cd_length, &N) != EOF && cd_length && N) {
		for (int i = 0; i < N; i++)
			scanf("%d", track + i);
		top = 0, minimum_space = cd_length, sum = 0;
		for (int i = 0; i < N; i++)
			max_length(cd_length, i);
		for (int i = 0; i < optimum_top; i++) {
			sum += optimum_cd[i];
			printf("%d ", optimum_cd[i]);
		}
		printf("sum:%d\n", sum);
	}
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: