その挑戦受けて立つ!!

アバター
tk-xleader
記事: 158
登録日時: 14年前
連絡を取る:

その挑戦受けて立つ!!

投稿記事 by tk-xleader » 13年前

掲示板のほうで、なんか挑戦状(丸投げっぽいが違う気がする…)が叩きつけられているので、受けて立とうと思います。

【1】 問題
長さnの数列Aと整数Mに対して、Aの要素の中のいくつかの要素を足しあわせてMが作れるかどうかを判定するプログラムを作成せよ。
Aの各要素は1度だけ使うことができる。
数列Aが与えられたうえで、質問としてq個のMが与えれるので、それぞれについて"yes"または"no"と出力せよ。
プログラムはC, C++, JAVA, C++11, C#, Dいずれかの言語で作成すること。

入力
 1行目にn、2行目にAを表すn個の整数、3行目にq、4行目にq個の整数Miが与えられる。
出力
 各質問についてAの要素を足しあわせてMiを作ることができればyesと、できなければnoと出力せよ。

制約
n ≤ 20
q ≤ 200
1 ≤ Aの要素 ≤ 2000
1 ≤ Mi ≤ 2000
解答

CODE:

import std.stdio;
import std.conv;
import std.string;

void main(){
	int n = to!int(stdin.readln().strip());
	int[] A = new int[n];
	string[] inputA = stdin.readln().split();
	for(int i = 0; i < n; i++){
		A[i] = to!int(inputA[i]);
	}
	
	int q = to!int(stdin.readln().strip());
	int[] Mi = new int[q];
	string[] inputMi = stdin.readln().split();
	for(int i = 0; i < q; i++){
		Mi[i] = to!int(inputMi[i]);
	}
	
	foreach(int x; Mi){
		writeln(A.findSum(x) ? "yes" : "no" );
	}
}

bool findSum(const(int)[] elements, int x){
	if(elements == null || elements.length == 0)return false;
	
	if(elements[0] == x)return true;
	
	return findSum(elements[1..$],x - elements[0]) || findSum(elements[1..$],x);
}
追記

"Don't repeat yourself."(コードの重複は避けよ)に従うと…

CODE:

import std.stdio;
import std.conv;
import std.string;

template InputArrayCode(alias LengthName, alias ArrayName){
	static immutable string InputArrayCode = r"int " ~ LengthName ~ r" = to!int(stdin.readln().strip());
	int[] " ~ ArrayName ~ " = new int[" ~ LengthName ~ r"];
	string[] input" ~ ArrayName ~ r" = stdin.readln().split();
	for(int i = 0; i < " ~ LengthName ~ r"; i++){
		" ~ ArrayName ~ "[i] = to!int(input" ~ ArrayName ~ r"[i]);
	}";
}

void main(){
	mixin(InputArrayCode!("n","A"));
	mixin(InputArrayCode!("q","Mi"));
	
	foreach(int x; Mi){
		writeln(A.findSum(x) ? "yes" : "no" );
	}
	
}

bool findSum(const(int)[] elements, int x){
	if(elements == null || elements.length == 0)return false;
	
	if(elements[0] == x)return true;
	
	return findSum(elements[1..$],x - elements[0]) || findSum(elements[1..$],x);
}
最後に編集したユーザー tk-xleader on 2012年5月24日(木) 01:47 [ 編集 2 回目 ]

アバター
tana
記事: 33
登録日時: 15年前

Re: その挑戦受けて立つ!!

投稿記事 by tana » 13年前

これはNP困難で有名な問題でしたっけ?
制約ないとやたら処理時間が長くなるとかいうのを講義で聞いた覚えがあります

アバター
tk-xleader
記事: 158
登録日時: 14年前
連絡を取る:

Re: その挑戦受けて立つ!!

投稿記事 by tk-xleader » 13年前

>tanaさん

なるほど、制約がないと処理時間が延びちゃいますか…
再起関数の使い方を見ると、確かにそのように思えますね。

アバター
GRAM
記事: 164
登録日時: 14年前

Re: その挑戦受けて立つ!!

投稿記事 by GRAM » 13年前

ナップサック問題でしたっけ?

アバター
みけCAT
記事: 6734
登録日時: 14年前

Re: その挑戦受けて立つ!!

投稿記事 by みけCAT » 13年前

どうみても半分全列挙(蟻本 P147参照)です。
本当にありがとうございました。

追記
あ、普通にメモ化探索でもできますね。
最後に編集したユーザー みけCAT on 2012年5月25日(金) 15:31 [ 編集 1 回目 ]

アバター
tk-xleader
記事: 158
登録日時: 14年前
連絡を取る:

Re: その挑戦受けて立つ!!

投稿記事 by tk-xleader » 13年前

>GRAMさん

そんな名前なんですね。僕はアルゴリズムの名前には疎いもので…

>みけCATさん

とても有名な問題なんですね。