<commit_before># ナップサック問題 
ナップサック問題とは，簡単にいうと与えられた入力と制約のもとで目的関数を最大化する問題のことです．
動的計画法を用いて最大値と組み合わせを出力します．
##例題
長さ`L`の金属棒が与えられるとして，この金属棒を切断したそれぞれを売りたい状況を考えます．
このとき，切り出した金属棒の長さに応じて，売るときの価格が分かっていて，切り出した金属棒の価格の合計を最も高くしたいとします．
この状況をナップサック問題に置き換えると，

* 入力 `切り出す長さと価格`:`InputSet[i].length & InputSet[i].price`
* 制約 `切り出した長さの合計<L`
* 目的関数 `切り出した金属棒の価格の合計を最大化`

となります．
同じ長さの切り出しはOKなので，これは個数制限無しのナップサック問題になります．
####入力例

<table>
    <tr>
        <td>長さ</td>
        <td>1</td>
        <td>2</td>
        <td>3</td>
        <td>4</td>
        <td>5</td>
        <td>6</td>
        <td>7</td>
        <td>8</td>
        <td>9</td>
        <td>10</td>
    </tr>
    <tr>
        <td>価格</td>
        <td>1</td>
        <td>5</td>
        <td>8</td>
        <td>9</td>
        <td>10</td>
        <td>17</td>
        <td>17</td>
        <td>20</td>
        <td>24</td>
        <td>30</td>
    </tr>
</table>

###個数制限無しナップサック問題
よくある0-1ナップサック問題とは違うので，コストテーブルを少しだけ変更します．
具体的には，`L`を超えない数だけそれぞれの入力を複製すればよいです．

例えば，`L=10`の場合，長さ1の切り出しに関しては，10回切り出せるため，長さ1の入力を10個に変更します．同様に長さ3の切り出しは，3回切り出せるので長さ3の切り出しを3個に変更します．このように変更することで，0-1ナップサック問題と同じアルゴリズムを適用できます．

##アルゴリズム

あとは動的計画法を用いて実装するだけです．
[knapsack.cpp][link_knapsack]を参照してください．

`>knapsack [number]`で入力例の`0<L<=number`の結果を出力します．

##出力

`0<L<=20`のときの出力結果→[result_20.dat][link_result]．

[link_knapsack]:https://github.com/romancek/algorithm/blob/master/knapsack/knapsack.cpp "実装のリンク"
[link_result]:https://github.com/romancek/algorithm/blob/master/knapsack/result_20.dat "出力例のリンク"<commit_msg>few changes<commit_after># ナップサック問題 
ナップサック問題とは，簡単にいうと与えられた入力と制約のもとで目的関数を最大化する問題のことです．
動的計画法を用いて最大値と組み合わせを出力します．
##例題
長さ`L`の金属棒が与えられるとして，この金属棒を切断したそれぞれ`(l_i * x_i)`を売りたい状況を考えます．
このとき，切り出した金属棒の長さに応じて，売るときの価格が分かっていて，切り出した金属棒の価格の合計を最も高くしたいとします．
この状況をナップサック問題に置き換えると，

* 入力 `切り出す長さと価格`:`InputSet[i].length, InputSet[i].price`
* 制約 `切り出した長さの合計 < L`
* 目的関数 `切り出した金属棒の価格の合計`

となります．
同じ長さの切り出しはOKなので，これは個数制限無しのナップサック問題になります．
####入力例

<table>
    <tr>
        <td>長さ</td>
        <td>1</td>
        <td>2</td>
        <td>3</td>
        <td>4</td>
        <td>5</td>
        <td>6</td>
        <td>7</td>
        <td>8</td>
        <td>9</td>
        <td>10</td>
    </tr>
    <tr>
        <td>価格</td>
        <td>1</td>
        <td>5</td>
        <td>8</td>
        <td>9</td>
        <td>10</td>
        <td>17</td>
        <td>17</td>
        <td>20</td>
        <td>24</td>
        <td>30</td>
    </tr>
</table>

<<<<<<< HEAD
##
動的計画法を用いて実装しています．
=======
###個数制限無しナップサック問題
厳密にいうと個数制限無しではないんですが，よくある0-1ナップサック問題`(x_i = 1 or 0)`とは違い，`x_i`が`l_i`によって変わる`(0 <= x_i <= L/l_i)`ため，コストテーブルを少しだけ変更します．
具体的には，`L`を超えない数だけそれぞれの入力を複製すればよいです．

例えば，`L = 10`の場合，長さ1の切り出しに関しては，10回切り出せるため，長さ1の入力を10個に変更します．同様に長さ3の切り出しは，3回切り出せるので長さ3の切り出しを3個に変更します．このように変更することで，0-1ナップサック問題と同じアルゴリズムを適用できます．

##アルゴリズム

あとは動的計画法を用いて実装するだけです．
>>>>>>> origin/master
[knapsack.cpp][link_knapsack]を参照してください．

`>knapsack [number]`で入力例の`0<L<=number`の結果を出力します．

##出力

`0 < L <= 20`のときの出力結果→[result_20.dat][link_result]．

[link_knapsack]:https://github.com/romancek/algorithm/blob/master/knapsack/knapsack.cpp "実装のリンク"
[link_result]:https://github.com/romancek/algorithm/blob/master/knapsack/result_20.dat "出力例のリンク"
{'fraction_non_alphanumeric': 0.17923635216156517, 'fraction_numerical': 0.03313348059324708, 'mean_word_length': 3.75975975975976, 'pattern_counts': {'":': 0, '<': 122, '<?xml version=': 0, '>': 112, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1310769', 'n_tokens_mistral': 2280, 'n_tokens_neox': 2204, 'n_words': 135}