Singapore NOI - Knapsack

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)$

Copy
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using std::cout;
using std::endl;
using std::pair;
using std::vector;

Copy
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());