トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

蟻本 - 動的計画法

[蟻本]

蟻本 - 動的計画法

  探索のメモ化と動的計画法

01ナップサック問題(重さの総和Wが大きい)

 重さと価値がそれぞれw,vであるようなn個の品物があります。
 これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。
  • 制約
    • 1 <= n <= 100
    • 1 <= w,v <= 100
    • 1 <= W <= 10000
  • テストケース
    • n = 4
    • (w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
    • W = 5
重さに対する最大の価値を計算する
計算量が O(nW) になる

サンプルコード

+ C++サンプルコード

+ Rubyサンプルコード

  漸化式を工夫する

01ナップサック問題(商品の重さwと総和Wが大きい)

 重さと価値がそれぞれw,vであるようなn個の品物があります。
 これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。
  • 制約
    • 1 <= n <= 100
    • 1 <= w <= 10^7
    • 1 <= v <= 100
    • 1 <= W <= 10000
  • テストケース
    • n = 4
    • (w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
    • W = 5
価値に対する最小の重さを計算する
計算量が O(nΣvi) になり、間に合う

+ C++サンプルコード

+ Rubyサンプルコード

  計算問題

お名前: コメント: