賞委員会は今年、総年間予算のうちn件の研究助成金を与える予定でした。しかし、予算はbドルまで削減されました。委員会のメンバーは、すべての助成金に最大限の上限を適用することにより、最低限の最高助成金の数に影響を及ぼすことを決定しました。委員会が助成金の総額を新しい予算と同等にするcの適切な価値を選ぶように助けてください。与えられた予算と助成金は最大上限値を見つける
私はこの問題をインタビューで尋ねられましたが理解できません。
このような問題に直面するときは、一度に1ステップずつ進めなければなりません。また、必要なことを理解できない場合は、インタビュアーに説明を求めてください。多くの場合、問題は意図的に曖昧になるため、インタビュアーは問題を解決しようとする前に問題の定義方法を確認できます。アプリケーション開発者としての仕事の一部は、アプリケーション構築の作業を開始する前に、明確かつ完全な要件を収集することです。
あなたはbドルを使用しており、以前に承認された最高額の補助金には、それぞれcドル以下の資金が必要です。明らかに、予算に残っている金額があれば、cドル未満の補助金が自動的に承認されます。
まず、以前に承認されたグラントを金額で降順にソートします。つまり、最高額の助成金がリストの先頭に表示されます。このようにして、できるだけ多くの最高価値付与を承認します。
その後、正面から始めてリストを参照し、額をcドル以上に上限を設定して承認します。調整後の金額が残りの予算以下であれば、その金額を承認します。擬似コードで
が、それは次のようになります。
grants = all grants sorted by amount, in descending order
remaining_budget = b
for each grant in grants
amount = grant.amount
// cap the grant amount to no more than c
if amount > c then
amount = c
if amount > remaining_budget then
// grant not approved
else
// approve grant
remaining_budget = remaining_budget - amount
end for