福袋っす(2)

LSLで無茶してみましたシリーズ最新作っすね。

自分の方法を載せておくっす。

問題点も書いておくっすね。

どうもぺんぎんっす( ◎v◎ )

何をやるかは前回の記事参照っす。

深さ優先探索で書いてみたっす。

list CONTENTS_AND_VALUES = // 景品(?)名, 価値 [価値の大きいもの順!]
  ["product10", 50,
  "product09", 50,
  "product08", 40,
  "product07", 40,
  "product06", 30,
  "product05", 30,
  "product04", 20,
  "product03", 20,
  "product02", 10,
  "product01", 10];
integer RANGE_MIN = 90; // 設定値の下限
integer RANGE_MAX = 110; // 設定値の上限

integer item_count; // コンテンツにある景品(?)総数

list bag; // 袋の中身
list result; // 探索結果格納用

// 初期化
Init()
{
  item_count = llGetListLength(CONTENTS_AND_VALUES) / 2;
}
// 探索制御
integer Search()
{
  integer i;
  for(i = 0; i < item_count; ++i)
  {
      bag = [i];
      DPS(i, llList2Integer(CONTENTS_AND_VALUES, i * 2 + 1));
  }
  if(result)
  {
      return TRUE;
  }
  else
  {
      return FALSE;
  }
}
// 深さ優先探索
integer DPS(integer prev, integer total)
{
  integer i;
  integer value;

  for(i = prev + 1; i < item_count; ++i)
  {
      // ピックした後の状態
      bag = [i] + bag;

      // 評価値を計算
      value = llList2Integer(CONTENTS_AND_VALUES, i * 2 + 1);
      total += value;

      // 再帰
      if(IsRange(total) || DPS(i, total))
      {
          result = [llDumpList2String(bag, ",") + "合計" + (string)total] + result;
      }

      // ピック前に戻す
      total -= value;
      bag = llDeleteSubList(bag, 0, 0);
  }
  return FALSE;
}
// 評価
integer IsRange(integer value)
{
  if(value >= RANGE_MIN)
  {
      if(value <= RANGE_MAX)
      {
          return TRUE;
      }
  }
  return FALSE;
}

default
{
  state_entry()
  {
      Init();
      if(Search())
      {
          llOwnerSay((string)llGetListLength(result));
          llOwnerSay(llDumpList2String(result, "\n"));
      }
  }
}

結果は全部まとめて1つのlistに格納しておいて

ダンプしてOwnerSayさせてるっすから、途中で切れちゃうかもっす。

関数DPS内のresultに結果を入れてる部分で

逐一OwnerSayさせた方が良いかもっすね。

60通りの組み合わせが出力されるはずっす。

これで全部網羅してるかというと、そうではないっす。

0,1合計100

っていうパターンがあるっすよね。

範囲内に収まってるっすけど、まだイケるっすね。

8番目または9番目の価値10を加えることも出来るっす。

自分の方法はこのオマケの部分を考慮してないっす。

また改良するかもしれないっすけど、とりあえずこんなもんで…