部分和問題

このタグの解説について

この解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

地上の洞窟•2ヶ月前

【Ruby】最小個数部分和問題を動的計画法で解く

1 2 3 4 5ここにある数字を好きに組み合わせて足していき、目標となる値を作れるか？そんな問題を「部分和問題」という。9を目標の数とする場合 1, 3, 5 2, 3, 4 4, 5 目標の数となる組み合わせはいくつかあり、その中でも4, 5が手っ取り早い。このような「目標の数を作るために、必要な数の個数は最小で何個か？」というのを考えるのが「最小個数部分和問題」である。これを「動的計画法」を用いて効率よく解く方法を解説する。動的計画法を使う 1. 表を用意する 2. 初期値を埋める 3. 各マスの計算実装個数制限あり個数制限なし個数制限あり・一次元配列個数制限なし・一…

#Ruby#動的計画法#部分和問題

ネットで話題

19ブックマーク足し算引き算で10を作るゲームと部分和問題、DP - 素人がプログラミングを勉強していたブログ

javascripter.hatenablog.com

関連ブログ

地上の洞窟•8ヶ月前

【Ruby】動的計画法を考える③「部分和問題」

10になるカードの組み合わせはある？数字の書かれたカードが並んでいる。この中から好きなカードを選び、書かれた数字の合計が10になる組み合わせは存在するか？このような「部分和問題」を「動的計画法」を使って効率よく解く方法を考える。部分和問題を考える実装ループビットDP →②ナップサック問題部分和問題を考える部分和問題はナップサック問題の一種として考えることができる。ナップサック問題では要素(荷物)に重さ価値という二つの属性があったが、部分和問題では「重さ=価値」として扱える。また、動的計画法にて計算をメモする場合、通常のナップサック問題では memo[i][j] = v …

#Ruby#動的計画法#DP#部分和問題

mathkyoproの日記•1年前

部分和の数え上げ

ランキング参加中数学ランキング参加中数学・科学・工学 (1) 競プロの問題として (2) 数学の問題として: 形式的冪級数 *1 (もう少し dp に寄せた方法) (3) 数学の問題として: 行列 2024/04/10 (3) を追記しました。次の問題を考えてみましょう。$1$ 以上 $5N$ 以下の整数の集合 $ \{1, 2, \cdots, 5N\} $ から$0$個以上の整数を選ぶ方法は$2^{5N}$ 通りある。このうち、以下の条件を満たす方法は何通りあるか。条件: 選んだ整数の集合の要素の和は $5$ で割り切れる。(ただし空集合の要素の和は $0$ と定める) (1) 競プロの…

#数学#数学III#競プロ#部分和DP#部分和問題

競技プログラミング日記•2年前

AtCoder Beginner Contest 216F

ABC216F $max(A_{S})$ と $sum(B_{S})$ をとる． $A$ をソートしておくと良さそう，ただしそれに合わせて $B$ も一緒にソートする． $i \in N$ を全探索して， $A_{i}$ が最大になる $S$ の取り方を調べる． $sum(B_{S}) \leq A_{i}$ になる様にすればよい．よって，以下のDPが良い． $dp[i][x] := [0,i)$ で見たときの， $B$ の部分和で $x$ 以下になるものの個数．これは部分和DPとほぼ同じで，初期化が異なるだけ． $dp[0][x] = 1$…

#AtCoder#AtCoder Beginner Contest#DP#sort#部分和問題

かなで技術日誌•2年前

部分和問題のビット全探索をやっと理解した

アルゴリズム力を鍛えるためにけんちょんさんの本を読んでいて、部分和問題のビット全探索でうまく理解できなかったので自分が理解できるまで調べたという話です。問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)作者:大槻兼資講談社Amazon より詳細な解説を読みたいのであればご本人のブログを読むのが良いかと思います。 drken1215.hatenablog.com 部分和問題でのビット全探索部分和問題について「部分和問題 (subset-sum problem)」は、要素が数値の集合 S において、要素の総和が M となる部分集合があるか判定する問題です。 www.nct9…

#アルゴリズム#Python#ビット演算#部分和問題