2次元配列、最初の項目の合計が求められ、2番目の項目の合計の最大値を求める

WBOY
リリース: 2016-08-10 09:07:18
オリジナル
1099 人が閲覧しました

以下の配列があります

リーリー

itemから4つの項目を取り出し、item[0]の合計が10になることを求め、item[1]の合計の最大値を求めます。

最適な解決策はありますか?

返信内容:

以下の配列があります

リーリー

itemから4つの項目を取り出し、item[0]の合計が10になることを求め、item[1]の合計の最大値を求めます。

最適な解決策はありますか?

アイデアがバックパックの問題で行き詰まっていたため、コードが表示されましたbug,即数量4满足,但总和为10并没有满足,实际情况是<=10...


元の回答:

この問題はバックパックの問題のように見えますが、実際にはバックパックの条件よりも厳しいものです。

すべて item的两个数可以分别对应背包问题里的weight(重量)value(价值)、ただしバックパックとは異なります:

1. たくさんitem只能选4个,即背包里只能装4个物品。
2.总重量严格要求等于10,而非小于等于10

そのため、今のところ、従来の動的計画法と貪欲なアルゴリズムに対応する解決策を考えることができませんでした。ここでは、貪欲なアイデアを利用した、しかし異なるアルゴリズムを示します。

1.

を入れます。 items按照item[1]的大小降序排列。
2.遍历items,并计算取得的item[0]的和,若大于10continue,否则添加斤最终结果result中,直到取出4

正直、私のこのコードには自信がありません

【最適解を保証するものではありません】 あくまでアイデアですので、他の専門家の方のご意見を頂きたいと思います。 ^0^

コードは次のとおりです:

リーリー

出力結果:

リーリー

以下は上記を踏まえて変更しておりますが、正確であることを保証するものではありません。 。 。

リーリー

出力結果:

リーリー

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート