--- id: 5a23c84252665b21eecc7ed3 title: ナップサック問題 / 連続 challengeType: 5 forumTopicId: 323654 dashedName: knapsack-problemcontinuous --- # --description-- 泥棒が肉屋に押し入り、商品の中から盗むものを選びます。 泥棒はそれぞれの商品の重量と価格を知っています。 泥棒は耐荷重に制限のあるナップサックを持ち込んでおり、耐えられる重量の範囲内で利益を最大化できる商品を選びたいと考えています。 商品は切ることも可能です。切ると、元の価格に応じ、質量比に合わせて価格が減少します。 つまり、商品を半分に切ると、その価格は元の商品の半値になります。 # --instructions-- 店に並んでいる商品を表すオブジェクトの配列を取る関数を記述してください。 各オブジェクトには商品名、重量、価格の 3 つの属性があります。 また、この関数はパラメータとして最大重量を取ります。 関数は価格が最大となる値を返す必要があり、選択した商品の総重量は最大重量を超えてはいけません。 # --hints-- `knapContinuous([{ "weight":3.8, "value":36, name:"beef" }, { "weight":5.4, "value":43, name:"pork" }, { "weight":3.6, "value":90, name:"ham" }, { "weight":2.4, "value":45, name:"greaves" }, { "weight":4.0, "value":30, name:"flitch" }, { "weight":2.5, "value":56, name:"brawn" }, { "weight":3.7, "value":67, name:"welt" }, { "weight":3.0, "value":95, name:"salami" }, { "weight":5.9, "value":98, name:"sausage" }], 10)` は `257.875` を返す必要があります。 ```js assert.equal( knapContinuous( [ { weight: 3.8, value: 36, name: 'beef' }, { weight: 5.4, value: 43, name: 'pork' }, { weight: 3.6, value: 90, name: 'ham' }, { weight: 2.4, value: 45, name: 'greaves' }, { weight: 4.0, value: 30, name: 'flitch' }, { weight: 2.5, value: 56, name: 'brawn' }, { weight: 3.7, value: 67, name: 'welt' }, { weight: 3.0, value: 95, name: 'salami' }, { weight: 5.9, value: 98, name: 'sausage' } ], 10 ), 257.875 ); ``` `knapContinuous([{ "weight":3.8, "value":36, name:"beef" }, { "weight":5.4, "value":43, name:"pork" }, { "weight":3.6, "value":90, name:"ham" }, { "weight":2.4, "value":45, name:"greaves" }, { "weight":4.0, "value":30, name:"flitch" }, { "weight":2.5, "value":56, name:"brawn" }, { "weight":3.7, "value":67, name:"welt" }, { "weight":3.0, "value":95, name:"salami" }, { "weight":5.9, "value":98, name:"sausage" }], 12)` は `295.05405405405406` を返す必要があります。 ```js assert.equal( knapContinuous( [ { weight: 3.8, value: 36, name: 'beef' }, { weight: 5.4, value: 43, name: 'pork' }, { weight: 3.6, value: 90, name: 'ham' }, { weight: 2.4, value: 45, name: 'greaves' }, { weight: 4.0, value: 30, name: 'flitch' }, { weight: 2.5, value: 56, name: 'brawn' }, { weight: 3.7, value: 67, name: 'welt' }, { weight: 3.0, value: 95, name: 'salami' }, { weight: 5.9, value: 98, name: 'sausage' } ], 12 ), 295.05405405405406 ); ``` `knapContinuous([{ "weight":3.8, "value":36, name:"beef" }, { "weight":5.4, "value":43, name:"pork" }, { "weight":3.6, "value":90, name:"ham" }, { "weight":2.4, "value":45, name:"greaves" }, { "weight":4.0, "value":30, name:"flitch" }, { "weight":2.5, "value":56, name:"brawn" }, { "weight":3.7, "value":67, name:"welt" }, { "weight":3.0, "value":95, name:"salami" }, { "weight":5.9, "value":98, name:"sausage" }], 15)` は `349.3783783783784` を返す必要があります。 ```js assert.equal( knapContinuous( [ { weight: 3.8, value: 36, name: 'beef' }, { weight: 5.4, value: 43, name: 'pork' }, { weight: 3.6, value: 90, name: 'ham' }, { weight: 2.4, value: 45, name: 'greaves' }, { weight: 4.0, value: 30, name: 'flitch' }, { weight: 2.5, value: 56, name: 'brawn' }, { weight: 3.7, value: 67, name: 'welt' }, { weight: 3.0, value: 95, name: 'salami' }, { weight: 5.9, value: 98, name: 'sausage' } ], 15 ), 349.3783783783784 ); ``` `knapContinuous([{ "weight":3.8, "value":36, name:"beef" }, { "weight":5.4, "value":43, name:"pork" }, { "weight":3.6, "value":90, name:"ham" }, { "weight":2.4, "value":45, name:"greaves" }, { "weight":4.0, "value":30, name:"flitch" }, { "weight":2.5, "value":56, name:"brawn" }, { "weight":3.7, "value":67, name:"welt" }, { "weight":3.0, "value":95, name:"salami" }, { "weight":5.9, "value":98, name:"sausage" }], 22)` は `459.5263157894737` を返す必要があります。 ```js assert.equal( knapContinuous( [ { weight: 3.8, value: 36, name: 'beef' }, { weight: 5.4, value: 43, name: 'pork' }, { weight: 3.6, value: 90, name: 'ham' }, { weight: 2.4, value: 45, name: 'greaves' }, { weight: 4.0, value: 30, name: 'flitch' }, { weight: 2.5, value: 56, name: 'brawn' }, { weight: 3.7, value: 67, name: 'welt' }, { weight: 3.0, value: 95, name: 'salami' }, { weight: 5.9, value: 98, name: 'sausage' } ], 22 ), 459.5263157894737 ); ``` `knapContinuous([{ "weight":3.8, "value":36, name:"beef" }, { "weight":5.4, "value":43, name:"pork" }, { "weight":3.6, "value":90, name:"ham" }, { "weight":2.4, "value":45, name:"greaves" }, { "weight":4.0, "value":30, name:"flitch" }, { "weight":2.5, "value":56, name:"brawn" }, { "weight":3.7, "value":67, name:"welt" }, { "weight":3.0, "value":95, name:"salami" }, { "weight":5.9, "value":98, name:"sausage" }], 24)` は `478.4736842105263` を返す必要があります。 ```js assert.equal( knapContinuous( [ { weight: 3.8, value: 36, name: 'beef' }, { weight: 5.4, value: 43, name: 'pork' }, { weight: 3.6, value: 90, name: 'ham' }, { weight: 2.4, value: 45, name: 'greaves' }, { weight: 4.0, value: 30, name: 'flitch' }, { weight: 2.5, value: 56, name: 'brawn' }, { weight: 3.7, value: 67, name: 'welt' }, { weight: 3.0, value: 95, name: 'salami' }, { weight: 5.9, value: 98, name: 'sausage' } ], 24 ), 478.4736842105263 ); ``` # --seed-- ## --seed-contents-- ```js function knapContinuous(items, maxweight) { } ``` # --solutions-- ```js function knapContinuous(items, maxweight) { function item_cmp(a, b) { const ua = a.unitVal, ub = b.unitVal; return ua < ub ? 1 : ua > ub ? -1 : 0; } items = items.map(({ value, weight }) => ({ unitVal: value / weight, weight })); items.sort(item_cmp); let val = 0; let wt = 0; for (let { unitVal, weight } of items) { var portion = Math.min(maxweight - wt, weight); wt += portion; var addVal = portion * unitVal; val += addVal; if (wt >= maxweight) { break; } } return val; } ```