Q&A
まず、重さはこちらを参考にするべきです。
https://www.mof.go.jp/currency/coin/general_coin/list.htm
5円硬貨の重さと有効桁数が違います。
また、今の状態だと丸投げです。
あと、例とすべきところが例外になってます。意味が全く違ってくるので併せて修正を。
背景
財布の中のお金が重さでわかったら便利だな～ なんて思いアルゴリズムを考えていたのですが、総当たり以外の方法に検討がつかなかったので良いアイデアがあればご提案いただきたいです。よろしくお願いいたします。
前提
日本では硬貨は以下6種あり、それぞれの重さは必ず以下の通りである。
| 名称 | 重さ |
|---|---|
| 一円硬貨 | 1g |
| 五円硬貨 | 3.7g |
| 十円硬貨 | 4.5g |
| 五十円硬貨 | 4g |
| 百円硬貨 | 4.8g |
| 五百円硬貨 | 7g |
はかりの誤差は考慮しないものとする。
問題
複数枚、複数種の硬貨がN[枚]あり、それらすべてを計測した時の重さはA[g]であった。
考えられる硬貨の合計金額を全て列挙せよ。
---追記start---
妥協が必要であれば，それはそれでありだと思います。
単なる疑問から質問したに過ぎないので妥協点は何でも良いです。
ここに目を瞑ればこんなやり方があるんだ というのも知りたいため
---追記end---
入力
N = 硬貨の合計枚数 A = 硬貨の合計の重さ[g]
出力
T = 合計の金額
例外
(N=)2枚の硬貨があり、合計の重さは(A=)2gであった。
出力
2
言語は何でしょうか？
まー・・・、まずは小数点以下があるかないか、で可能性あるコインが半分にできますね。
そっから、倍数的にそのコインがあり得るかどうかを算出して、限定。
そこから総当たり、にすれば、
計算量はだいぶ抑えられると思います。
@te2jiさん
実際の重さは問題の本質ではありませんので、全て異なるならばこのままで良いと考えます。
@miyabi_takatsukさん
アルゴリズムの問題ですので、実際のコードを問うものではありませんので、何でも良いです。
> まー・・・、まずは小数点以下があるかないか、で可能性あるコインが半分にできますね。
そっから、倍数的にそのコインがあり得るかどうかを算出して、限定。
これが妥当なラインですかね、、、
> 財布の中のお金が重さでわかったら便利だな～
が解決したい質問ですよね？
> 実際の重さは問題の本質ではありませんので、全て異なるならばこのままで良いと考えます。
とは、意味が分かりません。
どっかの課題ですか？
ちなみに造幣局の貨幣大試験での規定誤差を考慮すると、財布内の枚数がごく少数でなければ種別の判定は無理そうです。
https://ja.wikipedia.org/wiki/%E8%B2%A8%E5%B9%A3%E5%A4%A7%E8%A9%A6%E9%A8%93
@te2jiさん
本質ではない、というのは日本円の硬貨にしか通用しないものではなく、汎用的なアルゴリズムがあればそれを知りたいというわけです。もっと言えば、硬貨以外でもです。買い物カゴの重さから中身を推定して会計金額を出すとかね。
別にどっかの課題ではなくただ実用も意図していないただの疑問ですので、イチャモンしかつけれないようであればお構い頂かなくて結構でございます。私もそうですがエンジニアはできない理由、言い訳から考えがちですからねぇ。
知見のある方から面白い回答がいただけるのを気長に待つことにします。
> 買い物カゴの重さから中身を推定して会計金額を出す
質問とは何の関係も無いけど、数年前にアメリカのアマゾンかどこかの実店舗がやってましたね。ただ重さからは実質不可能なので（あと効率）、複数のカメラの映像を元に算出しているようですが。
kou0719さん、なんにせよ、この質問は、
自身の書いてみたコードがない限り、丸投げ作業依頼の域を出ませんので、
なんの言語でもいいので、自身で書いたコードをまずやってみて、記載しましょう。
コインの枚数が、多くなればなるほど、
組み合わせ爆発は避けられず、計算不能な気はしますけどね。
解が１つ見つかったときに「その解から一定距離の候補は探索しなくてよい」という枝狩りができそうにも思うけど，どうなんでしょうね．
仮に，
ある解から硬貨をK枚入れ替える(K枚へらして，代わりに減らした種類ではない硬貨をK枚増やす）ことでできる状態までの距離をKと呼ぶとすれば，とりあえず距離1は絶対に解にならない．
じゃあ距離2は…？ 距離３は…？ 現在の解と硬貨群の重さの定義からどうにかして判定できると思うのだけど…（やりかたはわからんですが）
※そんなことを頑張るよりも総当たりした方が早かったり？
@hantaimanさん
あーそれ，見た事あります。
画像認識，ICタグ等が実用的なやり方ではあるのかもしれません。
@miyabi_takatsukさん
そもそもコードの回答を求めている質問ではありません。
私の結論としてはお恥ずかしながら，
> 総当たり以外の方法に検討がつかなかったので
ですので…（Teratailはコードレビューサイトではないはず。）
組み合わせ爆発については，硬化種にもよりますが，まあ大抵は組み合わせ爆発になってしまい計算量は膨大なんだろうとは思います。厳密な解ではなくても最適解とかでも良いのかも？
@fanaさん
んんん，なるほど。
確実性はなくともアイデアがあればお手すきの時に是非ご回答頂けると幸いです！
> 厳密な解ではなくても最適解とかでも良いのかも？
と書いた手前すみませんが，そもそもこの問題に最適解など存在しなかった。。。すみません。
ただのありふれたナップザック問題ですね。課題でしょう。
@zuishinさん
ナップザック問題と異なるところは別に最大を求める訳ではない，という事ですね。
でもナップザック問題のアルゴリズムは参考になりそう，ありあとうございます。
そして課題ではないです。
もう面倒くさいのでこの手の妄想はこれ以降無視しますが学生ですらありません。
言い直します。
ただのありふれたナップザック問題の亜種ですね。課題でしょう。
????
> 財布の中のお金が重さでわかったら便利だな～ なんて思いアルゴリズムを考えていたのですが
> 実際の重さは問題の本質ではありませんので、全て異なるならばこのままで良いと考えます。
課題でなければここでうそをつく意味がないので。
それはキッカケではありますが，汎用的に考えたくなるのはエンジニアの性では？
普通にここで2020年現在の日本円硬貨しか通用しないアルゴリズム考えるのなんてイケてないでしょう。
Qiitaでは良い記事書いていらっしゃるのに大変残念でございます！！
硬貨の枚数が決まっていなければまだそれも通用したでしょう。汎用とは逆で制限が加わっています。
「硬貨の枚数が分かっている前提自体が汎用性が無い」という認識で合ってますかね？でしたらその通りです。
硬貨の枚数も分からない状態での方が汎用性はあるでしょうが，考えてみるといくら何でも解が膨大すぎる気がしたので入力パラメーターを増やした次第です。なくてもいけるなら無い方が良いです。
kou0179さん、残念ですが・・・、
> 良いアイデアがあればご提案いただきたいです。
の時点で、作業依頼に抵触してしまいます。
なぜなら、アイディアさえあれば、
後はコードを書くだけだからです。
つまり、そのアイディアの提案だけで、質問の回答の域を超えてしまう、ということです。
それくらい、難しい問題なのが正直なところで、
そこをクリアするために日夜、どこかでアルゴリズムの研究がなされています。
下手したら、大学で研究するレベルの話だと思いますよ。
（ナップザックなど、該当する概念はすでにあるのかもしれませんが）
@miyabi_takatsukさん
難しい問題なんですねぇ…
定石的な解法は無さそうですね。ありがとうございます。
@miyabi_takatsukさんに限ったメンションではありませんが，利用規約に抵触しているという意見については，Teratailは質問者も質問を削除できませんので，各人で運営に問い合わせていただければ幸いです。私は抵触していないと考えているので，削除リクエストを自分で出す事はしませんが。
ならば総当たりで解くコードを掲載してください。そうすれば枝刈りのアイデアを提供する回答者が現れるかもしれません。
では気が向いたら掲載します。以上です。
> 利用規約に抵触しているという
利用規約ではなく、「推奨されない質問」です。
つまり、禁止ではないけど、閲覧者
からの印象が悪くなりやすく、低評価を受けやすいため、回答を得るのが困難な質問、ということです。
https://teratail.com/help/avoid-asking
@miyabi_takatsukさん
なるほど，ご教示ありがとうございます。
もうコメントを見ればわかる通り，閲覧者の印象は悪いようですね。笑
なんか自分はここまで話してきた人が自分には難しくて分からないから，
論点をすり替えイチャモンつけたいようにしか感じないんですよね…
それは課題だろ！丸投げだろ！と。
別にそんな事無い人も多々いるのは分かってはいるのですが，もし分からなくてそういう事をしている方がいるなら構わないで頂きたいのです。
> なんか自分はここまで話してきた人が自分には難しくて分からないから，
> 論点をすり替えイチャモンつけたいようにしか感じないんですよね…
私にはまったく理解不能な行動原理ですが、そういう文化の人なんですね。
> N = 硬貨の合計枚数
課題かどうかは知りませんし特に気にしてませんでしたが、この条件がある時点で課題かどうかの疑いとは無関係に、質問に対する疑問が湧くことは自然だと思います
> 丸投げだろ！
質問者自身で考えた（合計枚数指定無しの）総当たりバージョンのコードを載せておくだけでも、丸投げと感じる人は激減するというか、いなくなるような気はしますね
> 妥協が必要であれば，それはそれでありだと思います。
単なる疑問から質問したに過ぎないので妥協点は何でも良いです。
「全探索で妥協する」というのも、条件によってはありかと思いますが、それで不満な点は具体的にどこにあるのでしょうか？
@maisumakunさん
「全探索で妥協する」でも良いと思いますよ。自分は計算量を考えた時に現実的ではなく思い，全探索以外の方法を模索しています。
ただ，今更ながら入力値の取りうる範囲を指定していないのでそもそも妥協点も考えにくいのかも。失礼しました。
全て列挙せよ ← ここを妥協しようｗ
@fana さん
ご回答頂きありがとうございます！
いやぁ，そこですよね。。。この時点で実質，厳密解を求めてるようなもんですからねぇ。
汎用的，汎用的と言い続けていましたがこの手の問題は，何を解決したいのか をもっと具体的にしないとダメなのかも。（ワンチャン持ちうる最大所持金を求めよ， とか笑）
> 何を解決したいのか をもっと具体的にしないとダメなのかも
そうですね、条件が限定されればされるほど、それに応じた合理的解決策が出てきます。
回答1件
0
ベストアンサー
- ある１つの解(:N枚でA[g]になる組み合わせ)が与えられ，
- 2<=M<=N なる全Mの値に関して，重量が等しくなる「あるM枚の硬貨の組み合わせ と 別のM枚の硬貨の組み合わせ」のパターンを全て事前に網羅できている
（例えば，質問文内の例においては，五円４枚の重さは 3.74 = 14.8g で，これは，｛百円１枚(4.8g)，十円２枚(4.52g)，一円１枚(1g)｝と等しい）
という条件においては，
ある解(1.)から出発して，現在の解を前記2.のパターンの１つを用いて更新していく，という探索方法が採れるように思う．
※However, 必要な事前条件(特に2.の側)に要する計算量が全探索レベルになりそうな気が……
投稿2020/10/27 01:31
編集2020/10/27 03:16総合スコア11708
あなたの回答
tips
プレビュー
