CODEWITHSUNDEEP
algorithmknapsack-problemgreedy
Peyman Tahghighi
Peyman Tahghighi

Reputation: 77

Knapsack problem with values per item and limited items

I'm trying to solve a variant of knapsack problem that i haven't seen before. in this variant we have a vector v consist of values per gram for each item and we also have a limited weight of each item and our goal is to find the maximum value that can be gain if we have a pack of size M. I tried greedy approached but haven't found any solution. i think the most difficult part is to do it in O(n) because we shouldn't sort anything. anyone has any idea?

Upvotes: 1

Views: 469

Answers (1)

Patrick87
Patrick87

Reputation: 28302

If the value per gram has reasonably narrow bounds, you can counting-sort or radix-sort or bucket-sort it in linear time by the value per gram, and then just fill up the bucket in order of most valuable substances. What do I mean by reasonable limits? Specifically, I mean that there are asymptotically fewer meaningful "values per gram" than there are kinds of substances.

Upvotes: 1

Related Questions