I’m trying to find max possible amount of weights which sum <= target sum.

Example:

```
weights = (3, 2, 5, 2, 1, 1, 3), target_sum = 10
3, 2, 1, 3, 1 -- (sum = 10) correct items because has max items
5, 2, 3 -- (sum = 10) not max amount of items
```

I’ve done the DP solution which can find max possible sum and max possible amount of items (which sum <= target sum).

But I’m really stuck to get the **max possible items which sum <= target** from DP.

I know how to get the any items. So **I did one trick with sorting**.

But I’m trying to find a way how it could be done **without sorting**.

Python code:

```
def max_subset_sum(ws, target_sum):
n = len(ws)
k = target_sum
dp = ((0) * (k + 1) for _ in range(n + 1))
count = ((0) * (k + 1) for _ in range(n + 1))
for i in range(1, n + 1):
for j in range(1, k + 1):
curr_w = ws(i - 1)
if curr_w > j:
dp(i)(j) = dp(i - 1)(j)
count(i)(j) = count(i - 1)(j)
else:
tmp = round(dp(i - 1)(j - curr_w) + curr_w, 2)
if tmp >= dp(i - 1)(j):
dp(i)(j) = tmp
count(i)(j) = count(i - 1)(j - curr_w) + 1
else:
dp(i)(j) = dp(i - 1)(j)
count(i)(j) = count(i - 1)(j)
return get_items(dp, k, n, ws)
def get_items(dp, k, n, ws):
# The trick which allows to get max amount of items if input is sorted
start = n
while start and dp(start)(k) == dp(start - 1)(k):
start -= 1
res = ()
w = dp(start)(k)
i, j = start, k
while i and w:
if w != dp(i - 1)(j):
res.append(i - 1)
w = round(w - ws(i - 1), 2)
j -= ws(i - 1)
i -= 1
return res
if __name__ == '__main__':
# 3 + 2 + 1 + 3 + 1 == 10 (preferable result set)
# 5 + 2 + 3 == 10 (not max amount of items)
xs = (3, 2, 5, 2, 1, 1, 3)
indexes = max_subset_sum(xs, 10)
result1 = (xs(i) for i in indexes)
print(result1) # (5, 2, 3)
# But in case if we have sorted amount:
xs_sorted = sorted(xs)
indexes = max_subset_sum(xs_sorted, 10)
result2 = (xs_sorted(i) for i in indexes)
print(result2) # (3, 3, 2, 1, 1)
```

Also, I have weird attempt to get max amount of items.

But it’s produces incorrect result which sums to `9`

: `(3, 1, 1, 2, 2)`

```
def get_items_incorrect(dp, count, k, n, ws):
start = n
res = ()
w = dp(start)(k)
i, j = start, k
while i and w:
# while dp(i)(j) < ws(i - 1):
# i -= 1
while ws(i - 1) > j:
i -= 1
if i < 0:
break
max_count = count(i)(j)
max_count_i = i
while i and w == dp(i - 1)(j):
if count(i - 1)(j) > max_count:
max_count = count(i - 1)(j)
max_count_i = i - 1
i -= 1
res.append(max_count_i - 1)
w = round(w - ws(max_count_i - 1), 2)
j -= ws(max_count_i - 1)
i = max_count_i - 1
return res
```

For convenience, `dp`

and `count`

for given example:

```
ws: (3, 2, 5, 2, 1, 1, 3), target_sum: 10
0, 1, 2, 3, 4, 5, 6
dp:
0: (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
1: (0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3)
2: (0, 0, 2, 3, 3, 5, 5, 5, 5, 5, 5)
3: (0, 0, 2, 3, 3, 5, 5, 7, 8, 8, 10)
4: (0, 0, 2, 3, 4, 5, 5, 7, 8, 9, 10)
5: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
6: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
7: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
count:
0: (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
1: (0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1)
2: (0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2)
3: (0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3)
4: (0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3)
5: (0, 1, 1, 2, 2, 3, 3, 2, 3, 3, 4)
6: (0, 1, 2, 2, 3, 3, 4, 4, 3, 4, 4)
7: (0, 1, 2, 1, 2, 3, 3, 4, 4, 5, 5)
```

Sorry for such long read & thank you for any help!