December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
368
■
11
章 新たな分類のアルゴリズム
i = n
w = W
while w >= 0:
choice = progress[w]
if choice == -1:
break
selections[choice] += 1
w -= items[progress[w]].weight
return (m[W], selections
11.2.4
分析
これらの解の性能は
O(n)
になると思うかもしれないが、実際はそうならない。
O(n)
を実現するには全体の実行を
c*n
に抑え、
c
が十分大きな
n
に対して定数であ
る必要があるからだ。実行時間は
W
にも依存する。つまり、いずれにせよ、入れ子
の
for
ループからわかるように解は
O(n*W)
となるということだ。選択した品物の
復元は
O(n)
なので全体の性能は変わらない。
これらの知見はなぜ重要だろうか。
0-1
ナップサック
問題では、
W
が個々の品物
の重量をはるか
に超える場合、品物を
1
度しか使えないが故に、無駄な反復を何度
も繰り返さないといけなくなる。無制限整数ナップサック問題の解にも同様な非効
率性がある。
1957
年に
George Dantzig
が、例11-3に示す無制限整数ナップサック問題の近
似解を提案した。この近似は、まず重量価値比を最大化する品物をナップサックに
詰めるべきだという直感に基づいている。実際、この近似は、動的計画法で見つか
る最大価値の半分より悪くならないことが保証される。実際には、結果は真の値に
極めて近く、実行は極めてに速い
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.