野に咲く名無し@転載禁止<>113b7<>2023/09/24 19:51:30 ID:8vdx0C90<>今日はこの論文🥺

https://imgur.com/a/oo1FNQc<>お勉強するよお🥺 野に咲く名無し@転載禁止<><>2023/09/24 19:52:05 ID:eqRCO5mi<>ナップサック問題😆<> 野に咲く名無し@転載禁止<><>2023/09/24 19:53:36 ID:1CcNqNO6<>なるほど、うんちだ🤔<> 野に咲く名無し@転載禁止<><>2023/09/24 19:54:08 ID:lFdxvp90<>すまん何語や<> 野に咲く名無し@転載禁止<>主<>2023/09/24 19:54:25 ID:8vdx0C90<>制約式はナップサック問題😍
最適化したい目的関数がΣじゃやくてmax-maxとかになってる😡
めんどくさいことしないで😡<> 野に咲く名無し@転載禁止<><>2023/09/24 19:54:39 ID:8vdxv2Jb<>数学の話?<> 野に咲く名無し@転載禁止<>主<>2023/09/24 19:55:08 ID:8vdx0C90<>これ有料の論文だから中身は写せないけど🥺
これ早く読み切りたいンダ<> 野に咲く名無し@転載禁止<>主<>2023/09/24 19:55:19 ID:8vdx0C90<>だいたい数学ンゴ<> 野に咲く名無し@転載禁止<><>2023/09/24 19:58:30 ID:eqRCO5mi<>計算機科学屋さん🥺❓<> 野に咲く名無し@転載禁止<>主<>2023/09/24 19:59:27 ID:8vdx0C90<> >>9
倉庫バイトのフリーター…🥺<> 野に咲く名無し@転載禁止<><>2023/09/24 20:01:00 ID:lFdxvp90<>英語読めるだけですごいのに数学かよ
ようやっとる😍<> 野に咲く名無し@転載禁止<><>2023/09/24 20:01:00 ID:eqRCO5mi<> >>10
お勉強えらい😆<> 野に咲く名無し@転載禁止<>主<>2023/09/24 20:01:12 ID:8vdx0C90<>でも計算機科学分野なンダ
来年大学院に再入学するから勉強してるンダ<> 野に咲く名無し@転載禁止<><>2023/09/24 20:02:24 ID:8vdxQRJM<>maxがなんだsexさせろ<> 野に咲く名無し@転載禁止<>主<>2023/09/24 20:02:56 ID:8vdx0C90<> >>14
sex関数😻<> 野に咲く名無し@転載禁止<><>2023/09/24 20:07:38 ID:Ml1C80Tm<>🔑🐦<> 野に咲く名無し@転載禁止<><>2023/09/24 20:11:50 ID:p70pILlm<>日本語でおk<> 野に咲く名無し@転載禁止<><>2023/09/24 20:14:52 ID:HMHUvxcS<>ぷゆでもわかるように教えて下さいぷゆ🥺<> 野に咲く名無し@転載禁止<><>2023/09/24 20:22:11 ID:a0SAu6O6<>英語出来ないから英語の論文はいつもネットで引っ張って翻訳かけちゃうの🥺<> 野に咲く名無し@転載禁止<>主<>2023/09/24 20:22:20 ID:8vdx0C90<>教えましょう😎

いろんな商品があって、それぞれの商品に価値と重さが設定されています
価値は高いほど嬉しくて、重さは少ないほど嬉しい

🥺:価値1、重さ10
😎:価値2、重さ3
😻:価値5、重さ8
😡:価値7、重さ10

あなたは重さ25まで持ち運ぶことができます
価値を最大にするにはどうやって商品を選ぶのが良いでしょうか?

これがナップサック問題🥺<> 野に咲く名無し@転載禁止<>主<>2023/09/24 20:23:56 ID:8vdx0C90<>https://imgur.com/a/uXorU46

このナップサック問題を数学的に表現すると、こんな感じになるんですね🥺<> 野に咲く名無し@転載禁止<>主<>2023/09/24 20:27:14 ID:8vdx0C90<>ナップサック問題では商品の価値を足し算して、価値の合計を大きくする問題だったんだけど
今回は、選んだ商品から一番価値の高いもの(最大値)を調べて、それを最大化するような商品の選びかたをかんがえましょうってもんだいです

上のはmax-maxの例で、実際には
商品の価値の最大値を最大化、商品の価値の最大値を最小化
商品の価値の最小値を最大化、商品の価値の最小値を最小化
の4パターンを計算したいと🥺<> 野に咲く名無し@転載禁止<>主<>2023/09/24 20:29:25 ID:8vdx0C90<>しかも今回は、商品の重さがc_iじゃなくて、a_i+λb_iになってます🥺
λは変数なので、商品の重さが一次関数的なものになってしまいました😭
最終的にはλも動かして最適値を求めるらしいですが、もううんちです<> 野に咲く名無し@転載禁止<>主<>2023/09/24 20:29:40 ID:8vdx0C90<>バイトの休憩時間終わったので行ってきます😭<> 野に咲く名無し@転載禁止<><>2023/09/24 20:30:57 ID:HMHUvxcS<> >>20
これだけならすぐに答えは出るだろうけど、数値を変動させるとなかなか解法が作れないから困ってるということぷゆか...?🥺<> 野に咲く名無し@転載禁止<><>2023/09/24 20:40:23 ID:SA0bOFed<>将来ビッグになりそう<> 野に咲く名無し@転載禁止<>主<>2023/09/24 20:47:46 ID:8vdx0C90<> >>25
数値が連続的(0.1,0.2みたいな細かい数字も取れる)なら簡単ぷゆ
🥺
価値/重さを計算して、効率の良いものから順に取れば良いだけなので
安くて高カロリーな食品を、1円単位のカロリーを計算して買う、みたいな感じだね

でも実際には商品を取る、取らないの2択しか選べません
0-1のどちらかしか選べないぷゆ🥺
そうなるとこの問題、実はすごく計算時間がかかるのです🥺<> 野に咲く名無し@転載禁止<><>2023/09/24 20:50:46 ID:dD0ZC990<>頑張ってねぇ🥺💦<> 野に咲く名無し@転載禁止<><>2023/09/24 20:52:18 ID:HMHUvxcS<> >>27
取る取らないと買う買わないの違いがよくわからないぷゆ...🥺<> 野に咲く名無し@転載禁止<>主<>2023/09/24 21:18:56 ID:8vdx0C90<> >>29
連続的っていうのは、例えば🍎を1g単位で買えるってことですね🥺
一方で今回は、🍎を1個買うか買わないか、でしか選べないってことです

https://dai1741.github.io/maximum-algo-2012/docs/dynamic-programming/
ここの最初の例がわかりやすいと思う🥺
問題サイズが大きくなると簡単じゃなさそうでしょ🥺<> 野に咲く名無し@転載禁止<><>2023/09/24 21:32:13 ID:8vdxBIO6<> >>20
😡
😎
😎
😎
😎
😎
🙌こうかな?!<> 野に咲く名無し@転載禁止<>主<>2023/09/24 21:50:07 ID:8vdx0C90<> >>31
たぶん正解👍
今回の例だと、価値/重さを計算して、一番コスパがいいのは「😡」
だけど「😡」を2個取っちゃうと、残りの重さが5になって効率が悪い
一番効率のいい「😡」を、敢えて1個に抑えなきゃいけないんだねえ🥺
こういう、敢えて取らないが発生するから難しいンダ<> 野に咲く名無し@転載禁止<>主<>2023/09/24 21:50:22 ID:8vdx0C90<>バイト終わった🎉<> 野に咲く名無し@転載禁止<><>2023/09/24 23:19:14 ID:SA0bOFed<> >>33
おつかれ🥺<> 野に咲く名無し@転載禁止<>主<>2023/09/25 00:58:55 ID:i5H10wL4<>今日は眠いし明日は頑張るはず…🥺<> 野に咲く名無し@転載禁止<><>2023/09/25 02:06:40 ID:trmwt0pF<>読めない🥺<>