Hmm randomisiert C' wählen mit ||C-C'||_1 = 1?
Irgendwann ist dann ja der "Wasserpegel" so weit gestiegen, dass du in einem lokalen Maximum hängen bleibst,
also könnte man abbrechen wenn <c, C'> <= W für alle C' mit ||C-C'||=1 ist...
Btw. c ist hierbei der Nutzenvektor...
edit:
Nochmal zum Greedy...
(Hoffe mal, dass das noch nicht geschrieben wurde

)
Im beschränkten Fall kann der beliebig schlecht werden, z.B. bei folgender Instanz:
Der Rucksack hat eine Kapazität von 1, du hast ein Item mit Profit und Gewicht epsilon und beliebig viele Items mit
Gewicht 1-epsilon/2 und Profit 1-epsilon
Das höchste Profit/Gewicht-Verhältnis hat dann das kleine Item, und dazu passt kein anderes mehr...
Für epsilon -> 0 geht dann auch der Profit gegen 0, obwohl 1 möglich wäre...