今日はこの論文🥺
https://imgur.com/a/oo1FNQc
ナップサック問題😆
なるほど、うんちだ🤔
すまん何語や
制約式はナップサック問題😍
最適化したい目的関数がΣじゃやくてmax-maxとかになってる😡
めんどくさいことしないで😡
数学の話?
これ有料の論文だから中身は写せないけど🥺
これ早く読み切りたいンダ
だいたい数学ンゴ
計算機科学屋さん🥺❓
>>9
倉庫バイトのフリーター…🥺
英語読めるだけですごいのに数学かよ
ようやっとる😍
>>10
お勉強えらい😆
でも計算機科学分野なンダ
来年大学院に再入学するから勉強してるンダ
maxがなんだsexさせろ
>>14
sex関数😻
🔑🐦
日本語でおk
ぷゆでもわかるように教えて下さいぷゆ🥺
英語出来ないから英語の論文はいつもネットで引っ張って翻訳かけちゃうの🥺
教えましょう😎
いろんな商品があって、それぞれの商品に価値と重さが設定されています
価値は高いほど嬉しくて、重さは少ないほど嬉しい
🥺:価値1、重さ10
😎:価値2、重さ3
😻:価値5、重さ8
😡:価値7、重さ10
あなたは重さ25まで持ち運ぶことができます
価値を最大にするにはどうやって商品を選ぶのが良いでしょうか?
これがナップサック問題🥺
https://imgur.com/a/uXorU46
このナップサック問題を数学的に表現すると、こんな感じになるんですね🥺
ナップサック問題では商品の価値を足し算して、価値の合計を大きくする問題だったんだけど
今回は、選んだ商品から一番価値の高いもの(最大値)を調べて、それを最大化するような商品の選びかたをかんがえましょうってもんだいです
上のはmax-maxの例で、実際には
商品の価値の最大値を最大化、商品の価値の最大値を最小化
商品の価値の最小値を最大化、商品の価値の最小値を最小化
の4パターンを計算したいと🥺
しかも今回は、商品の重さがc_iじゃなくて、a_i+λb_iになってます🥺
λは変数なので、商品の重さが一次関数的なものになってしまいました😭
最終的にはλも動かして最適値を求めるらしいですが、もううんちです
バイトの休憩時間終わったので行ってきます😭
>>20
これだけならすぐに答えは出るだろうけど、数値を変動させるとなかなか解法が作れないから困ってるということぷゆか...?🥺
将来ビッグになりそう
>>25
数値が連続的(0.1,0.2みたいな細かい数字も取れる)なら簡単ぷゆ
🥺
価値/重さを計算して、効率の良いものから順に取れば良いだけなので
安くて高カロリーな食品を、1円単位のカロリーを計算して買う、みたいな感じだね
でも実際には商品を取る、取らないの2択しか選べません
0-1のどちらかしか選べないぷゆ🥺
そうなるとこの問題、実はすごく計算時間がかかるのです🥺
頑張ってねぇ🥺💦
>>27
取る取らないと買う買わないの違いがよくわからないぷゆ...🥺
>>29
連続的っていうのは、例えば🍎を1g単位で買えるってことですね🥺
一方で今回は、🍎を1個買うか買わないか、でしか選べないってことです
https://dai1741.github.io/maximum-algo-2012/docs/dynamic-programming/
ここの最初の例がわかりやすいと思う🥺
問題サイズが大きくなると簡単じゃなさそうでしょ🥺
>>20
😡
😎
😎
😎
😎
😎
🙌こうかな?!
>>31
たぶん正解👍
今回の例だと、価値/重さを計算して、一番コスパがいいのは「😡」
だけど「😡」を2個取っちゃうと、残りの重さが5になって効率が悪い
一番効率のいい「😡」を、敢えて1個に抑えなきゃいけないんだねえ🥺
こういう、敢えて取らないが発生するから難しいンダ
バイト終わった🎉
>>33
おつかれ🥺
今日は眠いし明日は頑張るはず…🥺
読めない🥺