L. The Knapsack problem

Codeforces

IDCF10106L

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

To prepare for the ICPC World Finals 2017, your team attended to a training camp. Glauber "the drinker" Sokolov was the teacher, and all teams had to answer a form so he would know what topics were the best to teach. The first day was introductory and Glauber said he would just go over well-known topics. He said "I noticed you all answered that you knew the Knapsack problem very well, so here is a simple exercise about it, follows directly from the definitions. Solve the knapsack problem with repetitions.". More formally, given N types of items, each one with a weight and a cost, choose some items such that the sum of its weights does not exceed S, and the sum of costs is maximum. You may choose any number of items of each type. Solve Glauber's exercise. On the first line two integers N and S, the number of types of items and the maximum allowed weight. Each of the next N lines has two integers wi and ci, the weight and the cost of the ith type of item. *Limits* Print a single integer, the cost of the items you choose. ## Input On the first line two integers N and S, the number of types of items and the maximum allowed weight.Each of the next N lines has two integers wi and ci, the weight and the cost of the ith type of item.*Limits* 1 ≤ N, wi ≤ 103 0 ≤ S, ci ≤ 109 ## Output Print a single integer, the cost of the items you choose. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of item types. Let $ S \in \mathbb{Z}^+ $ be the maximum allowed weight capacity. For each $ i \in \{1, \dots, N\} $, let $ w_i \in \mathbb{Z}^+ $ be the weight and $ c_i \in \mathbb{Z}^+ $ be the cost of item type $ i $. Let $ x_i \in \mathbb{Z}_{\geq 0} $ denote the number of items of type $ i $ selected. **Constraints** $$ \sum_{i=1}^{N} w_i x_i \leq S $$ **Objective** Maximize: $$ \sum_{i=1}^{N} c_i x_i $$

API Response (JSON)

{
  "problem": {
    "name": "L. The Knapsack problem",
    "description": {
      "content": "To prepare for the ICPC World Finals 2017, your team attended to a training camp. Glauber \"the drinker\" Sokolov was the teacher, and all teams had to answer a form so he would know what topics were th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10106L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "To prepare for the ICPC World Finals 2017, your team attended to a training camp. Glauber \"the drinker\" Sokolov was the teacher, and all teams had to answer a form so he would know what topics were th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of item types.  \nLet $ S \\in \\mathbb{Z}^+ $ be the maximum allowed weight capacity.  \nFor each $ i \\in \\{1, \\dots, N\\} $, let $ w_i \\in \\math...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments