How Many Fillings Are Optimal
Each item has a weight and a value and may be used at most once. The bag holds at most
C total weight. Print the largest total value AND how many distinct subsets achieve it,
the count modulo 1000000007. Subsets are identified by position.
items (w=1 v=1) (w=1 v=1) (w=1 v=1), C = 2 -> 2 3
The maximum is 2, and three subsets reach it, one for each pair of positions.
## Why two passes do not work
Running problem #236 for the maximum, then counting separately with problem 483, fails: 483 counts subsets by TOTAL WEIGHT, and there is no single weight to ask about. The optimum can be attained at several different weights.
(w=1 v=1) (w=2 v=2) (w=3 v=3) with C = 3 answers 3 2: value 3 is reached by the
single (w=3 v=3) item at weight 3, and by (w=1 v=1) (w=2 v=2) also at weight 3. Both
happen to weigh 3 there, but (w=2 v=1) (w=3 v=1) (w=5 v=2) with C = 5 answers 2 2,
attained at weight 5 by the pair and at weight 5 by the single item.
So the count and the optimum have to be built together.
## Carrying a count beside the optimum
This is problem #453's recipe applied to knapsack:
val[t] = the largest value at weight exactly t, or unreachable
cnt[t] = how many subsets attain val[t] at weight exactly t
val[0] = 0, cnt[0] = 1, everything else unreachable
for each item (w, v):
for t from C down to w:
if val[t-w] is unreachable: skip
cand = val[t-w] + v
if cand > val[t]: val[t] = cand; cnt[t] = cnt[t-w] REPLACE
if cand == val[t]: cnt[t] = cnt[t] + cnt[t-w] ADD
The two branches are the whole problem. A strict improvement makes every previously counted subset irrelevant, so the count is REPLACED. A tie describes a disjoint family, so the count is ADDED.
Using += in both cases overcounts and = in both undercounts, and both produce a
number rather than an error.
## Reading the answer
Find the maximum over all reachable val[t], then SUM cnt[t] over every t whose
val[t] equals that maximum.
Reading one weight only undercounts whenever the optimum is attained at several weights, and that is the common case.
## The zero-value trap
(w=1 v=0) with C = 1 answers 0 2. The maximum value is 0, and TWO subsets reach it:
the empty one and the one holding the item.
Nothing about a value of 0 makes a subset not count, and a solution that treats "value 0"
as "nothing chosen" answers 1. The empty subset has to be counted as a subset, which is
what cnt[0] = 1 says.
## Cost
Time O(n C). Space O(C).