📗 -> 11/19
🎤 Vocab
❗ Unit and Larger Context
Tuned the hell out to debug assembly code for HWP
✒️ -> Scratch Notes
Can prove by contradiction:
Reqs for Proof
In order to prove a greedy algo, need to prove:
- Greedy first choice
- Suboptimality
They are not equivalent, can have one without the other
For dynamic programming:
- Only suboptimality needed
Step 1
Given opt solution to knapsack
OPT <= set items such that value is maximized and weight is valid
Step 2:
A = OPT - {x1}
Prove A is optimal for items S-{x1} with a bag capacity W-w[x_i]
Step 3:
Assume A is not optimal for S-{x1}
rev(B) > rev(A) by def optimality
Bu{x1} fits into nag W
rev(B) + V[x1] > rev(A) + V[x1]
strategy > rev(OPT) => contradiction
🔗 -> Links
Resources
- Put useful links here
Connections
- Link all related words