Overview

There are \(N\) types of strings, each with a given length \(L_i\) and stock quantity \(C_i\). We want to select some strings so that the total length is exactly \(W\). The goal is to minimize the number of strings used.

Analysis

This problem is a typical “bounded subset sum problem,” which is a variant of the knapsack problem. The objective is to achieve “exactly length \(W\)” while “minimizing the number of strings used.”

Issues with a Naive DP

The simplest approach is to consider the following DP:

• dp[i][w]: the minimum number of strings needed to achieve length \(w\) using strings up to the \(i\)-th type

However, this approach has \(O(N \cdot W)\) states, and under the constraints \(N \leq 100, W \leq 50000\), there are up to \(5 \times 10^6\) states. Furthermore, if we loop over the stock quantity \(C_i\) in the transitions, the computational complexity explodes.

Speeding Up Bounded Knapsack (Binary Technique)

To address this, we use a well-known optimization for bounded knapsack called the “binary method (counting technique).”

When an item can be used \(c\) times, we decompose it as follows:

\[ c = 1 + 2 + 4 + \cdots + 2^{k-1} + r \]

Here, \(1, 2, 4, ..., 2^{k-1}\) are powers-of-two quantities, and \(r\) is the remainder.

This allows us to process in \(\log c\) iterations instead of looping \(c\) times.

For example, if there are 13 strings of length 5:

\[ 13 = 1 + 2 + 4 + 6 \]

We decompose them and treat them as “composite items” of lengths 5×1, 5×2, 5×4, and 5×6.

This enables efficient transitions.

Algorithm

This problem is solved as a bounded knapsack problem with minimization of the number of strings.

DP Definition

• dp[w]: the minimum number of strings needed to achieve length \(w\)
  Initial values: dp[0] = 0, all others are \(\infty\)

Update Method

For each string type \(i\), decompose the stock quantity \(C_i\) using the binary method, and update the DP for each composite item.

Specifically: - Let add_length = L[i] * k, then - dp[j] = min(dp[j], dp[j - add_length] + k) (where j >= add_length)

Perform this update for all composite items. The final answer is dp[W].

Complexity

• Time complexity: \(O(N \cdot W \cdot \log(\max(C_i)))\)
  • For each item, the stock quantity is decomposed into \(\log C_i\) composite items, and for each one, the DP table is updated in reverse order
• Space complexity: \(O(W)\)
  • The DP table is a one-dimensional array of size \(W+1\)

Implementation Notes

• The DP table must be updated in reverse order (to prevent using the same item multiple times)

• The binary decomposition of the stock quantity starts with k=1 and proceeds with count -= k; k *= 2

• If dp[W] remains unupdated (\(\infty\)) at the end, output -1

  Source Code

import sys
import heapq
from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    W = int(data[idx])
    idx += 1
    
    L = []
    C = []
    for _ in range(N):
        l = int(data[idx])
        idx += 1
        c = int(data[idx])
        idx += 1
        L.append(l)
        C.append(c)
    
    # dp[i] := ロープの長さが i になるのに必要な最小の紐の本数
    # 初期値は無限大、ただし dp[0] = 0
    INF = float('inf')
    dp = [INF] * (W + 1)
    dp[0] = 0
    
    # 各アイテムについて処理
    for i in range(N):
        length = L[i]
        count = C[i]
        
        # カウンティングテクニックによる多重ナップサックの処理
        # count を 1, 2, 4, ... の和に分解して処理
        k = 1
        while k < count:
            # 長さ length*k のアイテムを1つ使うと考える
            add_length = length * k
            # 逆順に更新することで同じアイテムを複数回使わないようにする
            for j in range(W, add_length - 1, -1):
                if dp[j - add_length] != INF:
                    dp[j] = min(dp[j], dp[j - add_length] + k)
            count -= k
            k *= 2
        
        # 残りのcount分を処理
        add_length = length * count
        for j in range(W, add_length - 1, -1):
            if dp[j - add_length] != INF:
                dp[j] = min(dp[j], dp[j - add_length] + count)
    
    result = dp[W]
    if result == INF:
        print(-1)
    else:
        print(result)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.