Singapore NOI - Knapsack

Author: Kevin Sheng

Prerequisites

ExplanationImplemention

Explanation

Note that the bound on $S$ is rather small and that $1 \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 $\lfloor\frac{S}{i}\rfloor$ items for the set of all objects with weight $i$. So in total you will need to consider $\sum_{i=1}^S \lfloor\frac{S}{i}\rfloor$ items. This expression approximates to $\mathcal{O}(S \log S)$ as $\ln(1+S) < \sum_{i=1}^S \frac{1}{i} < 1 + \ln(S)$. Each item weight takes $\mathcal{O}(S)$ to process, making the total time complexity $\mathcal{O}(S^2 \log S)$.

Implemention

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

C++

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


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!