504. 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).

Constraints - `1 ≤ n ≤ 1000` - `0 ≤ C ≤ 2000` - `1 ≤ weight ≤ 2000` - `0 ≤ value ≤ 1000000`