スレ立てるまでもない質問はここで 149匹目

2018/05/18(金) 10:22:17.79

質問する前にGoogleで検索しましょう。 http://www.google.com/
プログラム・ソフトの使い方は PC 初心者板やソフトウェア板へ。
ウイルス、ハッキング・クラッキングを求めるような発言は禁止です。
Javascript は Web 制作板、CGI は Web プログラミング板へ。
業界談義、愚痴はプログラマ板へどうぞ。
ゲーム関係の話題はゲーム製作板へどうぞ。
ネタ、板とは関係の無い話題はご遠慮ください。

前スレ
スレ立てるまでもない質問はここで 148匹目
https://mevius.5ch.net/test/read.cgi/tech/1495618637/

注意「～と～はどっちの方が○いですか？」みたいなのは
このスレの粘着荒らしですので無視してください

VIPQ2_EXTDAT: checked:vvvvvv:1000:512:----: EXT was configured

2018/08/28(火) 23:43:37.93

状態を持つならオブジェクト(+メソッド)、持たないなら純粋関数。簡単なことだろ？

2018/08/29(水) 00:50:26.87

レオンハルト・オイラーを超える数学者になりたい。

2018/08/29(水) 01:04:09.37

プログラム技術が極限まで発達するとどうなるのでしょうか？

2018/08/29(水) 02:02:57.39

ウイルスセキュリティソフトは個人で開発することは可能ですか？

2018/08/29(水) 02:28:18.62

一生全く頭を使わないで生きていたらどうなるのでしょうか？
脳が萎縮するのでしょうか？

2018/08/29(水) 04:40:33.64

プログラムからプログラムを起動するときに起動引数を渡そうと思うんですが、
悪意あるプログラムが同じコンピューター上で動作していた場合、
起動引数を盗み見る事はどの程度困難ですか？
もしカーネルをハックするような動作が必要なら、恐らくアンチウイルスに引っかかると思うのですが。

2018/08/29(水) 05:05:48.84

タスクマネージャで見れるよ

2018/08/29(水) 10:15:53.98

設計的なことって独学じゃなかったらどこで教わるんだ？

**749です** (ｽｯｯﾌﾟ Sdff-7jYX [49.98.141.100]) · 2018/08/29(水) 10:23:18.71

>>774
本当にありがとうございます。

keyMaker{
private string password;
private encoding enc;
public createkey(){
passwordをバイト配列にencで変換
し、
長さ8の配列にxorしながら入れて鍵に
して返す
}
}

という感じだったのですが

password{
private string value;
tokey(encoding enc){
encでvalueをバイト配列に変換
し、長さ8の配列にxorしながら入れて
返す
}
}

という風に変えようと考えたのですが
どうでしょうか。少しはマシになっているのでしょうか。(encodingはpasswordクラスの属性でもいいかなというもしますが)

オブジェクト指向において名前の付け方がかなり重要(というか本質?)というような印象を受けますがこの認識はおかしいでしょうか。

2018/08/29(水) 11:57:39.86

各言語の入門書の次に読む本は「Effective 何々」
デザインパターン・設計の仕方なども、書いてある

これを読んでいないと、プロとは呼べない

上司に多いけど、たいてい、おかしな事を言ってる奴は読んでない

2018/08/29(水) 12:04:49.45

>>789
言語は何？そうするともう少し絞って話せるんだけど。。

名前付けは大切。
パスワード以外の用途には絶対に使わないか？とか。
encodingが文字列のエンコーディングだとすれば、それは引数に渡すべきじゃない。
コンストラクタで、中身とエンコーディングを渡すべき。
そもそもそれ、tokeyを呼ぶときに決定するものではないでしょ？

tokeyはホントに言語によってなんて言う言葉が適切かはわからないけど、JavaならgetKeyで、プロパティのある言語なら単にKeyでは？
あと、個人的にはToXXXは意味が広すぎると思う。AsKey()とかかなぁ。

2018/08/29(水) 12:06:27.45

encoding を、password インスタンス毎に変えて保存するなら、インスタンス変数にすべき

常に同じ、encoding を使うのなら、encoding 情報はいらない。
コメントに書くとか、クラス変数に保存しておく

このスレよりも、各言語のスレに書き込んだ方がよい

2018/08/29(水) 12:14:10.07

>>789
そりゃ重要なのは間違いないが
オブジェクト指向だから特に大切である、ということはないと思う

まあ、オブジェクト指向の中で比較的よく使われる設計（デザパタ）の中には
中身ほぼ同じでも名前で大きく運用が異なっちゃうような例外もあるにはあるが

2018/08/29(水) 13:01:16.02

>>791
ありがとうございます。実のところ、言語はvb.netを使っています
オブジェクト指向をサポートする言語でのクラスの基本的な設計が知りたかったため言語を記載しておりませんでした。

後だしで恐縮ですがもう少し具体的な話をすると、この鍵というのはDESを復号するためのものです
(セキュリティ上すでにDESが非推奨なのようですが、とりあえず練習ということで気にしないでください)

2018/08/29(水) 18:03:43.57

>>794
じゃあ拡張メソッドが使えるのか。
ならAsKeyを文字列の拡張メソッドにするか、文字列で作るパスワードクラスにして、元の文字列捨てちゃうかな。

しかしDESの鍵なら、ちょっきり128ビットなりにならないと駄目で、受け付ける文字列からそれをxorで作ってるなら、
せめてMD5とかSHAとかでhash取って使ったほうがいいんでないの？
xxxx....yyyy....と、yyyy....xxxx....がどちらも有効なパスワードになるんでは？

2018/08/29(水) 21:41:28.83

>>773
キーワードを与えて鍵を返すだけなら
クラスにすべきではないというのが私の考え
C言語なら関数にすればいい

キーワードを与えて鍵を得た後、
そのオブジェクトのデータを何かの形で継続利用するなら
（例：作成した鍵をバイト列とは異なる表現で得る）
オブジェクトのメンバー変数として保持しておくべき

ただコード全体をオブジェクト指向で統一しろと
言われうることも多いね

2018/08/29(水) 23:06:12.38

DESを復号化するための鍵？
意味が分からん。。。

そもそもDESは対称鍵暗号
暗号化も復号化も同じ鍵使う

2018/08/30(木) 01:17:14.19

無になってもう二度と有になりたくない。
自殺をしたら無になってもう二度と有にならなくなるのだろうか？
それとも、自殺をしたら地獄に落ちたり更に悲惨な状態でまた生まれてきたりするのだろうか？
どうなんだろう？

2018/08/30(木) 03:30:02.37

ハーバード大学数学科を首席入学&卒業したい。

2018/08/30(木) 10:56:34.64

>>797
失礼しました
暗号化/復号に使う鍵の間違いです

2018/08/30(木) 11:02:00.77

>>796
ありがとうございます。
javaやvb.netの場合その関数はどこに作るのがよいでしょうか
>>795
ありがとうございます。拡張メソッドの使い方を勉強してみます
また、セキュリティに関するアドバイスも大変勉強になります。主旨とずれるのでここでこれ以上の質問は避けますが、もう一度考え直すことにします

2018/08/30(木) 13:04:37.16

値保有する必要が無いなら単にstatic関数作って引数もらえばいいんじゃないの

2018/08/30(木) 14:37:29.78

それを誰が持つかが問題なのでは。
拡張メソッドも実のところ単なる静的関数だけど、usingしたソース(使いたいシーン)だけで出てくるメンバ関数に見える存在なので、
単にUtil.KeyUtil.ComputeKeyみたいな深いUtilクラス作るより収拾がつきやすいとか、
宣言無しでは使えないので依存関係が頭のusing(VBで何だったか忘れた)見るだけでわかりやすいとか、
それぐらいのメリットでしか無いし。

2018/08/30(木) 21:09:31.99

>>801
desクラスでも作ってそこにメソッド置けば？

2018/08/30(木) 21:16:56.18

deathよね～

2018/08/30(木) 22:28:53.54

class des {
public:
　static encript(char const* encrypt_key, char const* plain_text, char* encript_text);
　static decript(char const* decrypt_key, char const* encript_text, char* plain_text);
}

ﾃﾞﾃﾞｰﾝ

2018/08/30(木) 23:06:04.46

class des {
public:
　static int encrypt(char *encoded, const char *key, const char *raw);
　static int decrypt(char *decoded, const char *key, const char *encoded);
};

2018/08/30(木) 23:09:47.44

YouTubeを作った人は天才なのでしょうか？
自分も、YouTubeみたいな世界的な超有名サイトを作って、大金持ちになりたいです。
具体的にどうすれば良いですか？

2018/08/30(木) 23:10:05.69

異世界に飛んで無双状態で人生をやり直したい
https://mevius.5ch.net/test/read.cgi/tech/1535627585/

2018/08/31(金) 02:11:23.03

リーマン予想とかP≠NP予想とかを自分一人の力だけで証明したい。絶対に実現してやるからな。

2018/08/31(金) 23:09:51.16

C++でゲーム作りたいんだけどどうやるんですか？
DXナントカ使うしかないんですか？

2018/09/01(土) 08:26:44.25

最近気づいたんですが
プログラムを書こうとしても入門書で習ったコードとほぼほぼ同じようなものしか書けません…
この板でお勧めされてる入門書2冊を読み切ったのにです
もしかしたら、ただコードを暗記してるだけで本当は本の内容理解出来てないんじゃないか？とか色んな不安を感じてきてます
2冊も読んだら応用的なコードもそれなりに書けるとイメージしてたんですが・・
向いてないと言われればそれまでなんでしょうが……
色んなパターンのコードが書けるようになりたいです。何かアドバイス下さい
もうプログラミングを始めて1ヶ月経ちました

2018/09/01(土) 09:44:59.95

次の勉強はアルゴリズムかデザインパターンかってところじゃね

2018/09/01(土) 09:45:34.95

何か作りたいものはないのかな？
それを作るためには、あなたの知ってるパターンをどう使うのが適切か？
を自分で考える。

2018/09/01(土) 12:13:11.76

英語とかと似てる
本読むだけじゃ身につかない
コードをいっぱい書くしかない
やってる密度にもよるけど、始めて1ヶ月じゃそんなもんでしょ

2018/09/01(土) 13:02:33.96

>>812
プログラムは入力を受け取ってそれを表示するだけ
画像だろうが文字だろうが同じ
アドバイスなぞない

2018/09/01(土) 15:04:32.34

>>812
本を読んで教えてくれることをただ受けとるだけでは上手くなることはないだろう。
本を読んで、その中で疑問に思ったり、こんなことはでないのかなと思ったことはない？あるなら、実際にコードを書いてあれこれ試してみれば、自然と上達するはず。
そういうことが特に何もなくて自発的に書こうとすることがないなら、この先も厳しいと思う。

2018/09/01(土) 20:59:54.63

なるほど。実際に書く書かないで理解の差が出てしまっているんですね・・・
一応VisualStudioインストールして載ってるコードをそのまま写して実行とかはやってたんですけど
受け取ったアドバイスを見るにただ本のサンプルを写して終わりってのがあまり良くないんですね…
そこから何か自分で考えて色々書き換えて試すのが重要なんですね
作りたいものは綺麗なGUIアプリと漠然と決まってますが今まで読んだ入門本の知識を総動員しても
無理なのであまりイメージが沸かないですね…
とりあえず自分でコードを考えて書くのを意識しながら今読んでる入門書を読破してみたいと思います
アドバイス大変ありがとうございます

2018/09/01(土) 21:06:08.02

recaptchaみたいに、特定の画像をマス目に分けて、リンゴっぽく見えるものは？という質問をして
それのデータを蓄積するということをしたいのですが右も左も分かりません
Pythonの本とディープラーニングの本から始めればいいのでしょうか？
人間が画像を解析して、その結果をコンピュータに学習させ、人間には見えず、コンピュータには見えるものを浮かび上がらせる
ということがしたいです
たとえば人間は先入観のせいで、人間の尻を尻として理解しますが、コンピュータは人間の尻をリンゴそっくりだと判定するかもしれません

2018/09/01(土) 21:09:12.57

人間はおっぱいをお尻と理解するから
ちんちんが勃つ

2018/09/01(土) 21:11:11.27

おっぱいはおっぱいとして愛せよ

2018/09/01(土) 21:11:26.09

その無理なのでってのがまず何ができないかっていう具体的な質問に変わるだろ？

2018/09/01(土) 21:21:37.34

たとえばなｱﾌﾟﾘに
ｴﾛ画像ﾌｧｲﾙを入力する

機械学習使ってｴﾛ画像判定を行う
それがｴﾛ画像なら勃起ｱｲｺﾝ
それがｴﾛ画像でないなら勃起してないｱｲｺﾝ
を表示する

まずそういうのから始めたほうがいい

ｺﾚができたら自動ｴﾛ画像収集ｸﾛｰﾗｰに応用できる

2018/09/01(土) 21:32:07.66

>>822
今まで読んだ本がプログラミングの基礎の基礎的な構文、仕様を説明してる本で
アプリに繋がるような事が書いてる本ではなくて
GUIとかはまた別の構文とか習わなきゃ書けないと思うのでそれを意識してコードを書くのは
今の段階では無理という意味でいいました。まだ習ってないので飛躍してるかなっと思って
言葉足らずですいません

2018/09/01(土) 21:37:14.21

別の構文なんか不要
文法覚えたらあとは文法どおり関数を呼び出すだけだ
心配することはない　ｻﾙにでもできる

この板にいるｻﾙ程度の知能のﾔﾂﾗでもできる程度のことだからな

2018/09/02(日) 01:14:45.68

>>823
回答ありがとうございます
それでは機械学習の入門書から当たってみます
いくつかライブラリのほうを検索してみましたが言語はやはりPython率高いですね
ユーザーからも画像データを投稿して貰いたいので、最終的にはAWSなどを借りることになると思います

2018/09/02(日) 10:27:15.60

エロ動画を管理するGUIプログラムを作りたいです
主な機能は
・動画タイトルを参考にしてdmmからサムネイルを取得する
・ニコニコ動画のようにタグ付けを行い検索しやすくする

わからないことは
・どのようなプログラミング言語、GUIライブラリで可能なのか
ということです
最適ではないにしても可能であれば、PythonとTkInterを使おうと考えています
Pythonであれば他にも面白そうなことができると思うからです

以上よろしくお願いいたします

2018/09/02(日) 10:49:02.10

自分も似たような事悩んでた頃あったよ
本読んで勉強してとりあえずやりたい事（仕事）では最低限のものが書けるようになった
その都度調べてこっちのが綺麗にかけるとかパフォーマンス良いとか少し気を使ったモノが掛けるようになった
でも職場では周りに技術者て言える人はないしレビューみたいなシステムもない零細だからスキルが上がってるかは不安がある

結局なんで不安かって言ったら自分が趣味で作りたいと思えるものに結びつかなくて出来ることが仕事周りの極一部で止まってるから
何でも良いから色々と手を出して手を動かして作るのが大切と気づいた

2018/09/02(日) 14:05:37.54

Twitterのソースって公開されてますか？

2018/09/02(日) 15:03:10.46

スクレイピングなら、Ruby で、Selenium WebDriver で、ブラウザを操作する。
JavaScript のElectron とか

どちらにせよ画面は、HTML

2018/09/02(日) 16:01:49.19

まずは東大に入り、そこを断然トップの成績で卒業し、
院はハーバードかオックスフォードかケンブリッジあたりに入りたい。
教授に推薦してもらえるように頑張りたい。

2018/09/02(日) 23:41:59.42

他所で無視されたからここで聞くがスーファミのマリカーの3D表現の仕組みが分からん。
コース全体の地面の画像があってそれから切り出して遠近法ぽく表示してるの？

2018/09/03(月) 02:19:20.25

実際のマリオカートがどうやってるかは知らないが
画像の回転・拡縮、あとは台形のような変形ができれば可能っぽいな

レトロゲーム板あたりの人のほうがSFCの技術仕様には詳しそうではあるが

2018/09/03(月) 09:52:44.26

Ruby始めたんですが、ATOMとVS code、どちらを使えばいいのかわかりません……
ATOMと方がテーマが沢山あって、MOMOKAI NEOとかめちゃくちゃ見やすいです。でも重いし、あんまり使ってる人がいない印象です。
VS code ATOMより軽いですが、テーマに魅力がなく、機能的に ATOMよりどこが優れているのか分かりません。でも多くの人がVS codeを勧めているので、 ATOMよりそっちの方がいいのかな……というきもします。
好きな方を使えという話だとは思いますが、ご意見をください。

2018/09/03(月) 13:14:44.33

>>834
vim

2018/09/03(月) 13:45:18.03

>>834
そりゃVS Codeは
ATOMとかそのへんを参考の1つとして作られたものって言われてるしな
同じようなものになるのは当然

ただ腐ってもVS、IDEのデファクトスタンダードの名前を冠しているだけあって
最初からコーディングを前提に設計されているエディタだし
当然そういったコミュニティ（サポートや拡張機能）にも強い
最近はMSのOSS界隈への信頼もそれなりに高いしな

まあちょっと触ってみてATOMのほうが魅力的だと思うなら
素直にその魅力的な方を使うべきだろうな

2018/09/03(月) 15:21:22.45

オブジェクト指向のプログラミングはなぜメイン関数でインスタンスを作ってrunメソッドを呼ぶだけで動くのですか？
runがメイン関数ということですか？

2018/09/03(月) 16:35:38.48

>>837
非オブジェクト指向の関数で、main関数の中でとある関数を呼んだらソレだけで動きました
何故ですか

これに答えれるなら、それがそのまんま答えだ

2018/09/03(月) 17:49:39.64

そりゃ、Atom よりも、VSCode だろ。
使っている人数が多いから、拡張機能が充実してる

Ruby, JavaScript, HTML, CSS, DB, webサーバー、テストツールなど

2018/09/04(火) 09:50:53.47

定期運送用操縦士と電験一種はどっちの方が凄いですか？

2018/09/04(火) 10:17:29.89

>>840
こちらへどうぞ

異世界に飛んで無双状態で人生をやり直したい
https://mevius.5ch.net/test/read.cgi/tech/1535627585/

2018/09/04(火) 11:01:22.73

今、思索をしていて哲学上の壁にぶつかってしまっている状態。
どうすればここを突破できるのだろうか・・・・・・・・・・？
こういう時、どうすれば良いのだろうか・・・・・・・・・・・・？
ただひたすら思索を続けるしか方法は無いのだろうか・・・・・・・・？

2018/09/04(火) 11:07:40.28

紙に書く

2018/09/04(火) 11:11:47.30

果たして俺はここを突破できるのだろうか・・・・。

2018/09/04(火) 20:42:18.11

トッパ！てすげえ言いたくなるよな

2018/09/05(水) 02:09:54.61

「吶喊」もいいぞ

2018/09/05(水) 12:52:41.62

pythonのpipみたいにライブラリ管理できるコンパイル言語ある？
Cはできないよね…

2018/09/05(水) 12:55:31.57

Goとか？

2018/09/05(水) 12:57:06.69

>>848
Goはできるんだ
Cではできないよね？

2018/09/05(水) 14:36:08.30

nuget
arduino

2018/09/05(水) 20:44:07.73

ちょっと曖昧な質問なのですが。
動きのあるWebページを作成する言語はJavascript以外、何があるでしょうか？

2018/09/05(水) 20:50:24.85

HaxeとかWebGLとかあるよ。

2018/09/05(水) 21:20:16.36

ありがとう
ぐぐってみるわ

2018/09/05(水) 22:36:41.91

油井亀美也とデミス・ハサビスはどっちの方が頭が良いですか？

2018/09/06(木) 12:50:25.80

ロボットプログラマーになりたいんですが情報系じゃなく機械系に行った方がいいですまか？
知能ロボティクスやりたいです

2018/09/06(木) 15:11:54.86

>>855
どっちでもなれるから情報でいいよ

2018/09/06(木) 20:49:58.18

http://www.meiwasuisan.com/frame/

↑こういう感じの巨大画像掲示板を作って、
それの運営だけで生計を立てていきたいのですが、
こういう感じの巨大画像掲示板って作るのにどれくらいの時間がかかりますか？

2018/09/06(木) 21:02:07.56

自殺をするか迷う。

2018/09/06(木) 22:33:00.93

>>855
情報系だと純粋にソフトウェアだけをやってるところがある
機械系だといまどきプログラムを書かないところはない

両方やりたいなら機械系がいいのでは

2018/09/06(木) 23:53:05.84

モデリングと作曲が趣味なのでそれを活かしてゲームを作りたいと考えました
調べた結果unityに行き着きましたがどうやらc#が必要な様なので勉強したいのですが何から手をつけていけばいいのでしょうか
まずは本を買って読んでコードを写していけばいいですか？
プログラミングはプの字すら触れたことがありません

2018/09/06(木) 23:54:02.53

申し訳ありません
ゲーム関係の質問はngだったようですね
失礼しました

2018/09/07(金) 04:59:43.53

>>860
ゲームでもゲーム以外でも同じ
工作とかプラモデルなんかの感覚で、とりあえず手を動かしてみればいいと思うよ

2018/09/07(金) 12:29:58.49

誰か>>857の質問に答えてください。

2018/09/07(金) 12:41:21.82

>>863
人による

上手い人がやればマリオをワープなし20分でクリアできるが
下手な人は何時間もかかるどころか、クリアできない
https://rocketnews24.com/2016/11/18/827374/

2018/09/07(金) 12:56:53.96

>>863
それを作るにはサーバーサイドプログラミングの技術が必要
その技術をどの程度持ってるかで作り上げるのにかかる時間が大きく違う
それに経験やコーディングスタイル、作り方などなどでさらに制作期間が変わる

プログラミング知識なしから始めるということなら
プログラミング出来るようになるか未知数だから何とも言えん

青写真が出来てるなら企画書作って専門業者に依頼して
作ってもらうのが手っ取り早い

2018/09/07(金) 15:12:44.22

最低でも、数年は掛かる。
巨大画像掲示板なら十年

だって単純なツール・アプリじゃないだろ。
これは、データベースとか部品が組み合わさった、システムだろ

システムの運用構築だけで、Docker とか数十の技術がある。
LPIC, LinuC などの資格もある

情報処理資格も一杯ある。
資格を数個は取らないと、システム運用構築なんて無理

2018/09/07(金) 16:37:35.63

資格の名前言ってるやつってろくにアプリも作らずに資格の勉強を作成時間にしてそう
こんなのそこらへんに転がってる大学生が半年で作ってるよ

2018/09/07(金) 16:53:04.51

> こんなのそこらへんに転がってる大学生が半年で作ってるよ

それが本当なら腐るほどできてる。

2018/09/07(金) 17:17:08.68

掲示板システムを実装する人と企画や運営する人は別だろう
ひろゆきとかは後者じゃないの？
本当に掲示板作りたいなら作れる人探すのが早い

2018/09/07(金) 19:37:52.65

>>868
作るのは簡単だけど人を集めるのは難しいから誰もやらない

2018/09/07(金) 19:41:06.36

>>870
人集めは、そこらへんに転がってる大学生を集めればいいだけじゃなかったの？ｗ

2018/09/07(金) 19:42:55.71

>>871
？　人が集まるというのはユーザーが集まるかということなんだが、それを身内で固めるということ？

2018/09/07(金) 19:45:49.38

急に笑っとるけどヤバない？こいつ？

2018/09/07(金) 19:57:20.25

>>867
そこら辺に転がってる大学生は言い過ぎじゃないの
でも、必要なことが全部分かってる大学生なら半年あれば作れるだろうな

>>869
ひろゆきはPerlは使えるとどこかのスレで聞いたことある
ちゃんと実用的なコードを書けるかどうかは知らんけど

>>871
不特定多数のユーザーが集まらんと質問者の目的の
それだけで食ってくのは無理だろう

2018/09/07(金) 20:42:38.42

システム作るだけならすぐだけどパフォーマンスとかセキュリティとかちゃんとしようとすると大変

2018/09/07(金) 20:48:19.75

たかだか掲示板で大げさすぎやわw
でもこうゆうバカ結構多いからホンマは笑えん

2018/09/07(金) 20:49:08.60

そうだな。サマータイムごときで大騒ぎしていた人もいるしな

みたいな感じかね？

2018/09/08(土) 03:07:48.41

AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。

個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。

例えば解法
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが、
前半の動的計画法は貪欲法を成功させるための処方なのか？

普通の貪欲法はナップサック問題で必ずしも最適な答えを返さないよね？
現に、貪欲法しかしないコードを提出してみたら2問ほど間違えた。
動的計画法を前処理的に用いることで貪欲法を成功させる方法って知られてるの？(それがこの解法？)

動的計画法で品物の個数を min(m[i], MAX_V) としている (できる) 理由も分からない。

他の人もほとんどこの方法で解いてるから、知られてる方法なのかと思うが調べてもヒットしない。

2018/09/08(土) 08:45:43.57

プログラミング・コンテスト・チャレンジブック、第2版、2012

2-3 動的計画法に、ナップサック問題の変形が載ってる

n は個数で、W は重さの総和。
計算量O(nWW)を、O(nW)に落とす

アルゴリズムか、プログラミング・コンテストのスレに書き込めば？

2018/09/08(土) 09:11:13.03

>>879
すみません。
アルゴリズムのスレもコンテストのスレもまともに機能していないのでここで質問させてもらいました。

>>878の問題はその本に載ってる問題のバリエーションの一つで、ナップサックの容量が極めて大きいので O(nW) では TLE です。

その本では動的計画法で品物の重さの総和が i であるときの価値の総和の最大値を記録した動的計画法テーブルを作っているのですが、
>>878で述べている「前半の動的計画法」では品物の価値の総和が i であるときの重さの総和の最小値を記録したテーブルを作り、更にその後で貪欲法を適用しています。
つまり動的計画法を貪欲法のための前処理として使っていると読めるのですが、なぜそれで上手くいくのか分かりません。