帰ってきたネコブログ

例えば、こんな感じ。
100, 200, 250, 300の中から2つの値を選んで、
足した結果が指定された値以内で最大となる組み合わせの和を返す。
450以内だと、200と250による450を返す。
600以内だと、250と300による550を返す。
120以内だと、120以内になる組み合わせは存在しないので0を返す。

という訳で、適当な値をたくさん用意して、
適当に値を指定して、結果を得る方法を考えてみる。

use v5.10;
use strict;
use warnings;

# 適当なたくさんの値
my @data = ( 120, 400, 290, 360, 500, 800, 480 );

# この値以内で、足した結果が最も大きくなるペアの和を返す
my $target = $ARGV[0] // 650;

# まずは、ソート
@data = sort { $a <=> $b } @data;

my $i = 0;
my $j = scalar(@data) - 1;

say '@data = ', join(', ', @data);
say '$target = ', $target;
my $result = 0;
while ( $i < $j ) {
    my $total = $data[$i] + $data[$j];
    printf( "\$i=%d, \$j=%d, ", $i, $j );
    printf( "%d + %d = %d\n", $data[$i], $data[$j], $total );
    if ( $total < $target ) {
        # 今回の結果の方が目標に近い場合は、結果を更新する
        $result = $total if $result < $total;

        # 目標より小さいので、小さい方の値を大きくする
        $i++;
    }
    elsif ( $target < $total ) {
        # 目標より大きいので、大きい方の値を小さくする
        $j--;
    }
    else {
        # 目標と同じなので、これ以上探索する必要はない
        $result = $total;
        last;
    }
}

say 'result = ', $result;

実行するとこんな感じ。
$ perl aaa.pl
@data = 120, 290, 360, 400, 480, 500, 800
$target = 650
$i=0, $j=6, 120 + 800 = 920
$i=0, $j=5, 120 + 500 = 620
$i=1, $j=5, 290 + 500 = 790
$i=1, $j=4, 290 + 480 = 770
$i=1, $j=3, 290 + 400 = 690
$i=1, $j=2, 290 + 360 = 650
result = 650

目標を変えてみる（１）
$ perl aaa.pl 300
@data = 120, 290, 360, 400, 480, 500, 800
$target = 300
$i=0, $j=6, 120 + 800 = 920
$i=0, $j=5, 120 + 500 = 620
$i=0, $j=4, 120 + 480 = 600
$i=0, $j=3, 120 + 400 = 520
$i=0, $j=2, 120 + 360 = 480
$i=0, $j=1, 120 + 290 = 410
result = 0

目標を変えてみる（２）
$ perl aaa.pl 780
@data = 120, 290, 360, 400, 480, 500, 800
$target = 780
$i=0, $j=6, 120 + 800 = 920
$i=0, $j=5, 120 + 500 = 620
$i=1, $j=5, 290 + 500 = 790
$i=1, $j=4, 290 + 480 = 770
$i=2, $j=4, 360 + 480 = 840
$i=2, $j=3, 360 + 400 = 760
result = 770

ポイントは、たくさんの値をあらかじめソートして、
一番小さい値と一番大きい値の組み合わせからスタートしている点。
そこから、より大きくする方法、より小さくする方法は1つしかなくて、
途中でより大きくする、もしくはより小さくする方法も、
2つのうち片方は直前に行った組み合わせと重複するので、
$iと$jの変化から読み取れる通り、
探索のループ数は用意した値の数くらいになって、
すべての組み合わせを調べるよりは早くなる。

ただし、ソートする時間は、
入力が文字列の場合は、こんな感じで少しだけ削れるけど、
ボトルネックになる可能性がある。

という訳で、あとは$iと$jの初期値をなんとかして、
ループ数を減らすのがいんじゃないですかね！

おしまい。

カテゴリー: Perl, コンピューター by ネコ on 2013年12月18日 | タグ: アルゴリズム > メモ