I've got bad news. There's no hope for an algorithm whose worst-case running time is polynomial in the size of the weighted graph (unless P = NP, which seems unlikely).
Your problem is as hard as the knapsack problem, which has no polynomial-time algorithm (unless P = NP) when the input is represented in binary. The knapsack problem has a pseudopolynomial time algorithm, which means that there is an algorithm whose running time is polynomial in the numbers (but not polynomial-time in the size of the input). In your setting, that turns into an algorithm whose running time is polynomial in the size of the unweighted graph (with a massive number of edges) but not polynomial in the size of the weighted graph (with a small number of edges).
You could try expressing this as an integer linear programming (ILP) instance, and then solve with an ILP solver. It's possible that might yield a more efficient solution. The core idea is to introduce an integer variable $x_{i,j}$ that counts the number of impressions provided to company $i$ in tag $j$; then you can introduce a few linear inequalities to capture the problem's requirements.