FreeStyleWiki

漸化式を立てる練習(1)

[アルゴリズム,DP]

漸化式を立てる練習(1)

  参考

  お題

コイン問題

問題
額面がc1, c2,..., cm 円の m 種類のコインを使って、 n 円を支払うときの方法は何通りあるか?

+ 解答

ABC044 C - 高橋君とカード

問題
N枚のカード使って、選んだカードに書かれた整数の平均をAにする方法は何通りあるか?

+ 解答

01ナップサック問題

問題
重さと価値がそれぞれ Wi, Vi であるようなN個の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。

+ 解答

予算1000円でサイゼリヤに行って、同じものを頼まずに摂取できる最大のカロリーを求める

問題
金額とカロリーがそれぞれ Mi, Ci であるようなN個の食べ物があります。 これらの食べ物から、金額の総和が1000円を超えないように選んだときの、カロリーの総和の最大値を求めなさい。

これは実質01ナップサックと同じか

+ メニュー

+ 解答

天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」

問題
人員数と発注費用がそれぞれ Qi, Ri であるようなN社の下請け会社があります。 これらの会社から、プロジェクトの人員がMを超えるように選んだときの、費用の総和の最小値を求めなさい。

+ 解答

+ ソース