Knapsack
- 1. Problem E : Fractional Knapsack 圻宛魃 }猟m翫 盾基m翫、魃 盾h魃
- 2. }古勣 ? ナップサック} C 仝否楚 C のナップサックが匯つと、n の瞳麗 ┯？、 pi, 否e ciが嚥えられたとき、ナップ サックの否楚 C を階えない譴任いつかの瞳麗 をナップサックにめ、ナップサックに秘れた瞳麗 の､虜佑鰈邊鷸するにはどの瞳麗をxべば よいか々Wikipediaより哈喘 ? 崙s C 瞳麗は販吭に蛍護辛嬬 C ?否eはにもなりうる
- 3. ?否eが屎のみの栽 ? 瞳麗が販吭に蛍護辛嬬ならgreedyで盾ける C /否eが寄きいに圀に秘れれば措い /否e 否e 否楚
- 4. 徭苧な栽 ? ＋ 0 かつ 否e − 0 C 腎き否楚がpって､睿造る ★ (?S?)??? ? − 0 かつ 否e ＋ 0 C 腎き否楚がえて､睇呂る ★ (???)??!! ? = 0 かつ 否e = 0 C どうでもいい ★ ( ?_f)??? 巣 屎 屎 音勣 否e 巣 駅勣
- 5. 深える駅勣がある栽 ? > 0 かつ 否e > 0 ? < 0 かつ 否e < 0 C 駅勣かどうかが徭苧でない 巣 屎 屎 音勣 否e 巣 駅勣
- 6. 盾隈1 ? greedy C 屎の瞳麗 > 0 かつ 否e > 0 ? /否eが寄きいにxぶ C の瞳麗 < 0 かつ 否e < 0 ? /否eが弌さいにxぶ ? 返 1. 腎き否楚がなくなるまで屎の瞳麗を秘れる 2. 屎の瞳麗との瞳麗を揖じ否eだけ秘れる
- 7. 盾隈1 ? どこまでxぶか C 屎の瞳麗の/否e の瞳麗の/否e /否e 屎の瞳麗 腎き否楚 の瞳麗 否e ここまでxぶ
- 8. 盾隈2 ? の瞳麗の憲催を郡させる C < 0 かつ 否e < 0 のとき、､犯欸eの憲 催を郡させ、否eをやし、､pらす C つまり、の瞳麗を枠に秘れて、憲催郡した屎 の瞳麗があると深える ★ 屎の瞳麗しかoい栽に｢彭できる 歌深exPacksの指基
- 9. ジャッジ盾 ? 魃升61佩 (C++) ? m翫115佩 (C++) ? m翫59佩 (Java) ? m翫98佩 (Java, LP)