22 lines
854 B
C
22 lines
854 B
C
#include "knapsack.h"
|
|
|
|
int maximum_value(unsigned int maximum_weight, item_t *items, size_t item_count){
|
|
unsigned int current_capacity = 0;
|
|
unsigned int current_value = 0;
|
|
/* Account for bad pointer */
|
|
if(items == NULL){ return 0; }
|
|
|
|
/*
|
|
* Thought process:
|
|
* We want max value. We should be checking both as many high value objects as possible
|
|
* into the bag, as well as checking the most amount of small objects in the bag as possible.
|
|
*
|
|
* According to Wikipedia, the unbounded version problem is NP-complete; that is, it's
|
|
* impossible to have a catch-all solution that always spits out the right answer.
|
|
*
|
|
* This specific variation seems to be the "0-1 knapsack" variant (essentially), which means
|
|
* it's easier, but still not great.
|
|
*
|
|
* Several solutions exist online already
|
|
* */
|
|
}
|