You can formulate this variation of the knapsack problem as an Integer Program
Standard Knapsack problem:
Maximize sum(j) Value_j x X_j
subject to
sum(j) Wt_j x X_j <= C
X_j is integer
In your variation, X_j can only take on distinct values: {0, 1,3,5,...}
Formulating the constraint to limit X to take on odd values
Whenever there are these types of restrictions on values a variable can take, introduce 0/1 variables to handle these conditions.
For each item j
let's introduce a bunch of binary Y variables, and a couple of new constraints.
X_j - 1 Y_j1 - 3 Y_j3 - 5 Y_j5 ... - M Y_jm = 0
m is the largest value (odd number) that Xj can take.
And to limit X_j to assume one of these values, we add
Y_j0 + Y_j1 + Y_j3 + ... + Y_jm = 1 for each item j
Y_j0, Y_j1, Y_j3 ..., Y_jm are {0,1} (binary)
The variable Y_j0 is to allow X_j to take on the value 0.
The fact that C = n^2
ensures that we can come up with reasonable upper limits m
for each constraint.
You can now solve this modified knapsack with an integer programming solver. It will still look for the items in decreasing order of "value density" (value per kilo), while the constraints limiting it to odd values will kick in for certain boundary conditions.
Hope that helps.