UVa-624 : CD

UVa

問題概要

長さN(<20)の配列がある。部分列で、部分和がSを越えないような最大のものを選ぶ問題。

解法

全探索。タイブレークのルールをよく理解していないけど要素数の多い方を優先するようにしたら通った。

acceptされたコード

計算量O(2^N*N)。

#include <cstdio>
using namespace std;

const int MAX_N = 20;

int N, L;
int as[MAX_N];

bool init(){
	if(scanf("%d%d", &L, &N)==EOF){
		return false;
	}

	for(int i=0; i<N; i++){
		scanf("%d", as+i);
	}

	return true;
}

void solve(){
	int best = 0, maxi = 0;

	for(int bit=0; bit<(1<<N); bit++){
		int tot = 0;
		for(int j=0; j<N; j++)if( (bit>>j)&1 ){
			tot += as[j];
		}
		if(tot <= L && maxi <= tot){
			if(maxi < tot || __builtin_popcount(bit) > __builtin_popcount(best)){
				maxi = tot;
				best = bit;
			}
		}
	}

	for(int i=0; i<N; i++)if( (best>>i)&1 ){
		printf("%d ", as[i]);
	}
	printf("sum:%d\n", maxi);
}

int main(){
	while(init()){
		solve();
	}

	return 0;
}