Singapore NOI - Knapsack

Author: Kevin Sheng

Table of Contents

ExplanationImplemention

Explanation

Note that the bound on SS is rather small and that 1WiS1 \leq W_i \leq S, so we can group the items together by weight. After this, we can implement the knapsack problem on the grouped together items. We also sort items of the same weight by reverse value, as it is always optimal to select the item with greater value among two items of the same weight.

Note that you only need to consider the most valuable Si\lfloor\frac{S}{i}\rfloor items for the set of all objects with weight ii. So in total you will need to consider i=1SSi\sum_{i=1}^S \lfloor\frac{S}{i}\rfloor items. This expression approximates to O(SlogS)\mathcal{O}(S \log S) as ln(1+S)<i=1S1i<1+ln(S)\ln(1+S) < \sum_{i=1}^S \frac{1}{i} < 1 + \ln(S). Each item weight takes O(S)\mathcal{O}(S) to process, making the total time complexity O(S2logS)\mathcal{O}(S^2 \log S).

Implemention

Time Complexity: O(S2logS)\mathcal{O}(S^2 \log S)

C++

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using std::cout;
using std::endl;
using std::pair;
using std::vector;

Java

Warning!

Due to Java's (relatively) slow speed, this solution will often TLE on the last subtask.

import java.io.*;
import java.util.*;
public class knapsack {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer initial = new StringTokenizer(read.readLine());
int limit = Integer.parseInt(initial.nextToken());
int typeNum = Integer.parseInt(initial.nextToken());
HashMap<Integer, ArrayList<int[]>> byWeight = new HashMap<>();

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!