AOJトライに関する知識知見の記録共有 （Volume0-0042）

概要

A Thief

コード

TIPS：ビット演算での探索パターン制御

def ret_value_weight_items(items, w_limit=-1):
    items = sorted(items, key=lambda x: -x[1])
    le = len(items)
    ret = []
    for ptnbit in range(pow(2, le)):
        its = [items[i] for i in range(le) if (ptnbit>>i)%2 == 1]
        #print(its, ptn)
        value, weight = [sum([v[idx] for v in its]) for idx in [0, 1]]
        if weight <= w_limit:
            ret.append([value, weight, its])
    return ret

def core(args, nbests=3):
    w_limit = args[0]
    items = args[1]
    value_weight_items = ret_value_weight_items(items, w_limit=w_limit)
    return sorted(value_weight_items, key=lambda x: (-x[0], x[1]))[:nbests]

def app(*args):
    return [[arg, core(arg)] for arg in args]

from pprint import pprint
pprint(app(
[50, [[60,10],[100,20],[120,30],[210,45],[10,4]]],
[60, [[60,10],[100,20],[120,30],[210,45]]],
))

実行結果

デバッグログ出力部含む

[[[50, [[60, 10], [100, 20], [120, 30], [210, 45], [10, 4]]],
  [[220, 49, [[210, 45], [10, 4]]],
   [220, 50, [[120, 30], [100, 20]]],
   [210, 45, [[210, 45]]]]],
 [[60, [[60, 10], [100, 20], [120, 30], [210, 45]]],
  [[280, 60, [[120, 30], [100, 20], [60, 10]]],
   [270, 55, [[210, 45], [60, 10]]],
   [220, 50, [[120, 30], [100, 20]]]]]]

補足

残課題：探索途中での枝刈り高速化