Hk=1+1/2+1/3+．．．+1/k
Harmony is the concept. I often read articles about brain computers. This is the new era of the computer science, and it is beyond calculation. I don't usually calculate anything at all even in paying my bills because of automation. Math was just copying the formula in my school days. The concept was philosophy. Your brain may be just algorism of repeating. I hope your existence must be more than that.
We know that an optimal solution covers all elements with solution weight OPT.
The average weight ≦ OPT/n
When k elements are covered, the optimal solution have n-k elements.
Remaining uncovered elements with an average weigh ≦ OPT/n-k
The greedy algorithm ≦ OPT/n-k+1
∴
Then we formalize the intuition.
This is expansion of uncovered elements.
wj is the covered weight.
∴
0 件のコメント:
コメントを投稿