[Programmers][python] 9. 解答練習(4):プログラマーキャンディを含む

3000 ワード
アルゴリズム問題 コンポジット python programmers テキストリンク
誤りに対する批判、質問、討論を歓迎します.自由にコメントを残しておきましょう!!

プログラマー-キャンディ


問題の説明

mグラム入りのバッグにキャンディがいっぱい入った数を作りたいです.しかし、同じキャンディはもう入れられません.
バッグが耐えられる重量m、キャンディの重量の配列重量をパラメータとする場合は、バッグが正確にmグラムで満たされている場合に数を返す解決関数を作成します.

せいげんじょうけん

  • mは1000以上100000以下の自然水です.
  • すべてのキャンディの重量が10以上100000以下の自然水です.
  • weightsの長さは3または15以下です.

    • I/O例


    mweightsreturn3000[500, 1500, 2500, 1000, 2000]3

    I/O例説明


    1種類のキャンディを選んで3000グラムを作る方法は[500、1000、1500]、[1000、2000]、[500、2500]の3種類がある.

    の意見を打診

  • mおよびweightsの範囲は広いが、入力サイズではないので無視できる.
    リストweightsの最大長は非常に小さく、15のみである.
    この場合,数値を抽出するアルゴリズムを用いることができる.

  • したがって、from itertools import combinationsパッケージを使用して、状況の数を組み合わせて問題を解決します.
  • for反復文の長さはweightであり、weightsから抽出された数を制御し、すべての場合の数をcomリストに保存する.
  • のすべての状況を確認し、選択した総数がmであることを確認します.

    • Code (Python)

    from itertools import combinations

def solution(m, weights):
    answer = 0
    for i in range(len(weights)):
        com = list(combinations(weights, i+1))
        for j in com:
            if m == sum(j):
                answer += 1
    return answer

    この記事は、プログラマーアカデミー人工知能Defcosコースで学んだ内容をもとにまとめたものです.
    Linux下プロセス間通信実験
    Dockerインストールチュートリアル(Ubuntu 18.04)