プログラミングは初めてです。

よろしくお願いします。

コンテナ A B C D E
耐久度 10 20 15 12 8
現在の負担 100 80 60 60 88

コンテナごとに耐久度があり
そのコンテナの耐久度×荷物の重さがそのコンテナの負担になります。
上のようにDBに値を持つ場合
重さの違う荷物を数十個振り分けていくとして
一番負担の少ないコンテナに振り分けるようにしたいのですが
どのようにくめば良いのか悩んでいます。。

重さ10の荷物が来たときは

A 100+10*10 =200
B 80+20*10 =280
C 60+15*10 =210
D 60+12*10 =180
E 88+8*10 =168

で合計の値の小さいEに振り分けて、Eの負担が168になり
また次の荷物を振り分けていきます。

言語はperlです。
何か良い実装方法があれば教えてください。
よろしくお願いします。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2012/01/29 10:20:14
  • 終了:2012/02/05 10:25:08

回答(2件)

id:uwao No.1

uwao回答回数171ベストアンサー獲得回数362012/01/30 05:19:48

こんなのはどうでしょう。
%taikyuu = (
'A' => 10,
'B' => 20,
'C' => 15,
'D' => 12,
'E' => 8);
%fuka = (
'A' => 100,
'B' => 80,
'C' => 60,
'D' => 60,
'E' => 88);
@hashkeys = keys %taikyuu;
@hashkeys = sort @hashkeys;
#重さが10,11,12の荷物が来たとき
foreach $_(10,11,12){
undef $minikey;
undef $minifutan;
foreach $hashkey(@hashkeys){
$futan = $fuka{$hashkey} + $fuka{$hashkey} * $_;
if(!$minifutan or $futan < $minifutan){
$minifutan = $futan;
$minikey = $hashkey;
}
}
$fuka{$minikey} += $taikyuu{$minikey} * $_;
}

id:k-ten87 No.2

k-ten回答回数2ベストアンサー獲得回数02012/01/30 20:10:08

自分の勉強がてら書いてみた。

#!/usr/bin/env perl

package Container;

use Moose;

has _initial_load => (is => 'ro',
		      isa => 'Int',
		      required => 1);
has _persistence => (is => 'ro',
		     isa => 'Int',
		     required => 1);
has name => (is => 'ro',
	     isa => 'Str',
	     required => 1);
has weight => (default => 0,
	       is => 'rw',
	       isa => 'Int',
	       writer => '_weight');

around BUILDARGS => sub {
  my $orig = shift;
  my $class = shift;

  if (@_ == 3) {
    my ($name, $initial_load, $persistence) = @_;
    return $class->$orig(_initial_load => $initial_load,
			 _persistence => $persistence,
			 name => $name);
  } else {
    return $class->$orig(@_);
  }
};

sub add_weight {
  my $self = shift;
  my $weight = shift or die;

  $self->_weight($self->weight + $weight);
  return $self;
}

sub clone {
  my $self = shift;

  return Container->new(_initial_load => $self->_initial_load,
			_persistence => $self->_persistence,
			name => $self->name,
			weight => $self->weight);
}

sub load {
  my $self = shift;

  return $self->_initial_load + $self->weight * $self->_persistence;
}

package main;

use Modern::Perl;

my $container = [Container->new('A', 10, 100),
		 Container->new('B', 20, 80),
		 Container->new('C', 15, 60),
		 Container->new('D', 12, 60),
		 Container->new('E', 8, 88)];

foreach my $weight (10, 11, 12) {
  (sort {$a->clone->add_weight($weight)->load <=>
	   $b->clone->add_weight($weight)->load}
   @$container)[0]->add_weight($weight);
}
  • id:windofjuly
    うぃんど 2012/01/29 13:47:52
    専門用語で何と言ったっけ?・・・と検索してみると「ビンパッキング問題」ですね
    http://ja.wikipedia.org/wiki/%E3%83%93%E3%83%B3%E3%83%91%E3%83%83%E3%82%AD%E3%83%B3%E3%82%B0%E5%95%8F%E9%A1%8C
    >>
    様々な解決方法(アルゴリズム)が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない(NP困難問題)
    <<
    >>
    アルゴリズムA
    1.荷物を空いている容量が最大のビンに詰める。
    2.どのビンにも荷物が入らないとき、新しいビンに詰める。
    <<
    >>
    アルゴリズムB
    1.荷物を空いている容量が最小のビンに詰める。
    2.どのビンにも荷物が入らないとき、新しいビンに詰める。
    <<

    以上、ヒントのみで逃げます(笑)
  • id:kokorohamoe
    特に指定が無いですが・・・最終的に現在の負担の最大値が最も低くなるようにしろという事ですよね?
    それがないと、全て E に突っ込むのが 最適解になってしまいます。

    オーダーが数十なら、私の大好きな総当りですかね。どのようなケースについても漏れが無いですし。
    ザルく考えても5^100回で回答が出ますので 
    荷物を桁数 箱の位置を数値ととらえて n桁の5進数の問題としてForをぶん回して 最小値とその組み合わせだけをminで比べていく
    000...000~555...5555の 演算のループで解けるとは思います。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません