締切済み

部分和問題について

2021/06/15 01:16

部分和問題の問題例と、その問題の動的計画法に基づくアルゴリズムによる解を１つ教えて頂きたいです。

iidabashiHAKASE
お礼率0% (0/1)

C・C++・C#
回答数1
ありがとう数0

みんなの回答 （1）
専門家の回答

みんなの回答

NuboChan
ベストアンサー率47% (790/1658)

2021/06/16 09:27 回答No.1

例えば、 https://qiita.com/gushwell/items/02a6ee994eacf3d9d3e0

関連するQ&A

部分和問題がわかりません。

部分和問題がわかりません。 [問題] n個の整数が配列Aに格納されていて、整数xの値を与えたときに、 A[i] + A[j] = x となるi,jが存在するかどうかを判定する、なるべく効率のよいアルゴリズムを示せ。この問題は部分和問題のため、NP完全問題なので、総当たりのO(n^2)より効率のいい方法がないと思うのですが、もっと効率のよい方法が存在するのでしょうか？
ニュートン法の問題がどうしてもわからないので教えてください。

非線形方程式の解を求めるアルゴリズムのひとつに、ニュートン法と呼ばれる方式がある。この方法ではf(x)=0の解の近似値を次の漸化式から求める。 x_(i+1) =x_i - f(x_i)/f'(x_i) なぜこのアルゴリズムで解を得られるのかをf(x)=x^2 - e^x -2 =0 を例に説明せよ。という問題です。どなたかわかる方がいたらお願いします。
因数分解と部分分数の和に関する問題

因数分解と部分分数の和に関する問題 f(x)=x^5-3x^4+5x^3-5x^2+3x-1の時、(1)因数分解せよ　(2)(x^3-3x+3)/f(x)を部分分数の和に分解せよ。という問題です。(1)については、f(1)=0より、f(x)=(x-1)(x^4-2x^3+3x^2-2x+1)に因数分解できるのですが、さらに因数分解できるのでしょうか？　(2)については、部分分数の和に分解するポイントはどうすれば良いのでしょうか？すみませんが、よろしくお願いします。
マスの和の問題

まずは添付のマスをお読みください。この９マスにはすべて数字が入っています。分かっている３つの数字がマスの中に示されています。このマスの縦、横、斜めの３つの数字の和が全て等しくなるとき、この値を求めなさい。このような問題に取り組んでますが、解は６６で答えに書いてあるのでわかるのですが解き方がわかりません。わかる方いらっしゃいましたらおねがいいたします。
数列の和の問題がわかりませんσ(^_^;

1/{4・3^(n+1)}の数列で k=1でn項までの間で和を求める問題なのですがどう解けばいいかわかりません。どなたか解答例を頂けないでしょうか？ちなみに答えは 1/24{1-(1/3)^n}です。どなたかお願いします。
シンプレックス解法の問題

大学で生産計画の問題で次のような問題が出て解き方がいまいちわかりません。答えと解き方をなるべく分かりやすくお願いします。問題：次の一般型生産計画法を２段階シンプレックス解法で解け。目的関数 z=1080y1+600y2+900y3 →最小化する制約条件式 9y1+4y2+3y3≧70 4y1+5y2+10y3≧120 y1 y2 y3≧0 （1）第１段階線形計画法を定式化し、最適解を求めよ。（2）第２段階線形計画法を定式化し、最適解を求めよ。
フーリエ級数の部分和

フーリエ級数の問題で、階段関数＝1(0<x<π) 　　　　　0(x=0) -1(-π<x<0) の第ｎ部分和をグラフに描いて収束状況を検討したいのですが、参考になるサイトかヒントをくださる方がいらしたらよろしくお願いします。
整数の和？の問題

1～300までの和から、 6で割り切れる数の和を引いたものを求めなさいという問題がありました。試験問題だったため、この手の問題の解き方を私は知らないため、 6の倍数を除いた1～300までの数を全て足したのですが結局500ほどどっかで計算ミスが生じ（後半であることは察しがつきますが）まだ残り時間はあったのと計算ミスしちゃったか～と落ち込んでいた時に、この問題は5択問題で選択肢を見ていたら、全部37000台だったのと下1桁が5択全て異なったため下1桁だけ足せば良かったんだなと気付きました。結局残り時間は他の問題の見直しに使いました（気力が持たず）で、家に帰ってきて、母に公式なんかがあるのか聞いたところ公式？を教えてもらい、そういえば前にもどっかで耳にしたなと思い出しました。で、300の和の出し方は301×150と分かったのですが計算ミスしたとはいえ300まで足した私としては 6の倍数、計50個を足して、301×150から引くことはさほど問題ではないのですが 1～300までの6の倍数の和を求める式はあるのでしょうか？
級数和の問題

(1)級数　Σ[n=1~∞]1/nは発散することを示せ。 →積分判定法により、発散 (2) m桁の自然数のうち0が入らないものの個数を答えよ。１つの桁に対して、１～９までの9通りの入り方があるので、9^m個を踏まえて、 (3) (1)の和から、nに0の文字が入った項(1/10,1/20など)を抜いた級数をSとする。このSが収束することを示せ。という問題です。(3)について教えてください。
線形計画問題

変数の数が２個、制約が３本の不等式からなる線形計画問題で、無限解を生成する例にはどんなものがあるのでしょうか？
数学の和の問題です。

数学の和の問題です。 Σ n*α＾n　（n＝１、２、…N　　　αは定数）上の和を何か１つの式にまとめることができるでしょうか例えばΣ α＾n＝α（１－α＾n∔1）/１－αみたいな感じです。よろしくおねがいします
高速な和積形命題論理式の含意関係判定法

２つの和積形命題論理式が与えられています。この２つの式に含意関係が成り立つか判定したいのです。この問題はco-NP完全問題でまともにやるととても時間がかかります。そこで次のような条件を満たすアルゴリズムを考えてください。１．アルゴリズムが含意関係がなりたつと答えたときは必ず含意関係が成り立つ。２．アルゴリズムが含意関係が成り立たないと答えたときは含意関係が成り立ってても成り立たなくてもよい。３．入力の多項式時間で停止する。この条件だけだと常に含意関係が成り立たないと答えるアルゴリズムでもOKになってしまいますがもちろん本当に含意関係が成り立つときはなるたけ含意関係が成り立つと答えてほしいわけです。私が考えたのは和積形の論理式ｆ、ｇがあたえられたとしてfのすべての和項に対してgにそれを含意する和項があったらgはｆを含意するというものです。これよりもよい方法を考えてください。よろしくお願いします。
部分分数の和に分解

現在、部分分数分解で問題が解けなくて困っています。問：　x^3-3x+3/f(x) を部分分数の和に分解せよまずf(x)=x*g(x)とおき与式をx^3-3x+3/x*g(x)と変形し A/x+(bx^2+cx+d)/g(x)と分解します。ですがこの後どうやっていけばいいのかがわかりません。なんか部分分数の基本的なところから理解が足りてない気がします。どなたかご指導のほどよろしくお願いします。
数列の和の問題です。

数列の和の問題なんですが、　1　　　1　　　　1　　　　　　　　　　　1 --- + --- + ---- ・・・・・・ + ----------- 4*1　　4*7　　7*10　　　　　　　(3n-2)(3n+1) 書き方がいたなくてわかり難いと思います。すみません。ただテストでもこのような問題をよく見かけるため、答えをと言うより解き方を教えてほしいです。（解き方を教えるのにこの問題を解いてもらいながらが理想ですけど・・・・・）お願いします。
教えてください。部分空間の問題です

ベクトル空間Vから w1,…,wnをVの真の部分空間としてとると、（w1,…,wnの和集合）≠Vを示せ。という問題です。また「真の」とはどういう意味でしょうか？
動的計画法と整数ナップサック問題

動的計画法によって、以下の整数ナップサック問題を解きなさい maximize　 8x1+9.5x2+11.5x3+14x4 subject　to　2x1+3x2+4x3+5x4≦7 　　　　　　　　xi∈｛0,1,2・・・}, i=1,2,3,4 大学院試験のアルゴリズムの過去問にこういう問題があるのですが、自分は数理計画法を学んでいないので全くわかりません。解放を教えてください。
「和菓子」もしくは「和菓子屋さん」に何を求めますか？

「和菓子」もしくは「和菓子屋さん」に何を求めますか？あなたは和菓子が好きですか？嫌いですか？またその理由はどうしてですか？和菓子屋さんにどんな商品があったらいいと思いますか？どんなサービスがあったらうれしいと思いますか？子供や若い世代にもっと和菓子を楽しんでもらうにはどうしたらいいと思いますか？具体的にあなたがファンな和菓子はありますか？（例：大福　または○○屋のXX饅頭　など）和菓子に対する希望・批判などどんな小さなことでもかまいませんのでご回答いただきたいと思います。よろしくお願いいたします。
数列の和を求める問題

次の和を計算せよ。Ｓ＝1/2＋2/2^2＋3/2^3＋4/2^4＋5/2^5＋6/2^6 という問題ですが、このパターンを見たのは初めてなのでどこから手をつけてよいのかわかりません。もしかしたらＳを何倍かして引くんでしょうか。どなたかよろしくお願いします。
線形計画問題

最近線形計画法について独学で勉強を始めたのですがいくつかの書籍を調べてもどうしても分からない点があったのでこの場を利用させて頂きます。頭を悩めていますのは制約条件が特殊なためです。問題を簡略すると以下のようになっています。 min : x(1)/2 + 5x(2)/2 suject to: 1/x(1)+1/4x(2) ≦ 8 x(1) ≧ 0, x(2) ≧ 0 御覧頂けますように制約条件において決定変数が分母にきているのです。目的関数で分母に変数を持つものは分数計画問題といるのを拝見した事があるのですが上記のような例は探し方が悪いのか見つける事ができていません。実行可能領域は非有界ですが最小化問題のため上記の例であると2変数なのでグラフにプロットする事でおよそですが解は見つかりました。しかし実際の問題は10変数以上の問題となっていますので解が求められません。その後も実行可能領域を多面体で近似すれば良いのか等の考察を繰り返しましたが問題が複雑になりお手上げの状態です。ちゃんとした解法があるのならお教え頂けるか書籍の案内をして頂きたいです。宜しくお願いします。
数学B いろいろな数列の和の問題について

こんにちは！数学Bの問題について困っている部分があるのて、質問させていただきます。 1・1+3・4+5・7+……+(2n-1)(3n-2)の、和を求めよという問があったとき、(画像)までは分かるのですが、そのあとの共通のものてまとめるときのことが、分かりません。この問いの場合、1/2nでまとめれるようなのですが、どう考えたら1/2がスルッと出てくるのでしょうか？？ややこしい質問になってしまいましたが、解説を、お願いしますm(__)m

部分和問題について

みんなの回答

関連するQ&A

部分和問題がわかりません。

ニュートン法の問題がどうしてもわからないので教えてください。

因数分解と部分分数の和に関する問題

マスの和の問題

数列の和の問題がわかりませんσ(^_^;

シンプレックス解法の問題

フーリエ級数の部分和

整数の和？の問題

級数和の問題

線形計画問題

数学の和の問題です。

高速な和積形命題論理式の含意関係判定法

部分分数の和に分解

数列の和の問題です。

教えてください。部分空間の問題です

動的計画法と整数ナップサック問題

「和菓子」もしくは「和菓子屋さん」に何を求めますか？

数列の和を求める問題

線形計画問題

数学B いろいろな数列の和の問題について

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

部分和問題について

みんなの回答

関連するQ&A

部分和問題がわかりません。

ニュートン法の問題がどうしてもわからないので教えてください。

因数分解と部分分数の和に関する問題

マスの和の問題

数列の和の問題がわかりませんσ(^_^;

シンプレックス解法の問題

フーリエ級数の部分和

整数の和？の問題

級数和の問題

線形計画問題

数学の和の問題です。

高速な和積形命題論理式の含意関係判定法

部分分数の和に分解

数列の和の問題です。

教えてください。部分空間の問題です

動的計画法と整数ナップサック問題

「和菓子」もしくは「和菓子屋さん」に何を求めますか？

数列の和を求める問題

線形計画問題

数学B いろいろな数列の和 の問題について

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

数学B いろいろな数列の和の問題について

カテゴリ
一覧

専門家に質問してみよう
専門家登録