Knapsack

Explicación

Notemos que la cota de $S$ es bastante pequeña y que $1 \leq W_i \leq S$ , así que podemos agrupar los ítems por peso. Después de esto, podemos implementar el problema de la mochila (knapsack) sobre los ítems agrupados. También ordenamos los ítems del mismo peso por valor inverso, ya que siempre es óptimo seleccionar el ítem de mayor valor entre dos ítems del mismo peso.

Notemos que solo hay que considerar los $\lfloor\frac{S}{i}\rfloor$ ítems más valiosos para el conjunto de todos los objetos de peso $i$ . Así que en total habrá que considerar $\sum_{i=1}^S \lfloor\frac{S}{i}\rfloor$ ítems. Esta expresión se aproxima a $\mathcal{O}(S \log S)$ ya que $\ln(1+S) < \sum_{i=1}^S \frac{1}{i} < 1 + \ln(S)$ . Cada peso de ítem toma $\mathcal{O}(S)$ para procesarse, lo que hace que la complejidad temporal total sea $\mathcal{O}(S^2 \log S)$ .

Implementación

Complejidad temporal: $\mathcal{O}(S^2 \log S)$

C++Java


#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
int main() {
	int limit;
	int type_num;
	std::cin >> limit >> type_num;
 
	std::map<int, vector<pair<int, int>>> by_weight;
	for (int t = 0; t < type_num; t++) {
		int value;
		int weight;
		int amt;
		std::cin >> value >> weight >> amt;
		if (weight <= limit && amt > 0) { by_weight[weight].push_back({value, amt}); }
	}
 
	/*
	 * best[i][j] contiene el mayor valor que podemos
	 * obtener usando peso j y los primeros i tipos de peso
	 */
	vector<vector<long long>> best(by_weight.size() + 1,
	                               vector<long long>(limit + 1, INT32_MIN));
	best[0][0] = 0;
	int at = 1;
	for (auto &[w, items] : by_weight) {
		// ordenamos los ítems en orden inverso por valor
		std::sort(items.begin(), items.end(), std::greater<pair<int, int>>());
		for (int i = 0; i <= limit; i++) {
			best[at][i] = best[at - 1][i];
			int copies = 0;
			int type_at = 0;
			int curr_used = 0;
			long long profit = 0;
			// recorremos tantos ítems como podamos hasta que nos quedemos sin ítems o
			// sin peso usable
			while ((copies + 1) * w <= i && type_at < items.size()) {
				copies++;
				profit += items[type_at].first;
				if (best[at - 1][i - copies * w] != INT32_MIN) {
					best[at][i] =
					    std::max(best[at][i], best[at - 1][i - copies * w] + profit);
				}
 
				curr_used++;
				if (curr_used == items[type_at].second) {
					curr_used = 0;
					type_at++;
				}
			}
		}
		at++;
	}
	cout << *std::max_element(best.back().begin(), best.back().end()) << endl;
}


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<>();
		for (int t = 0; t < typeNum; t++) {
			StringTokenizer item = new StringTokenizer(read.readLine());
			int value = Integer.parseInt(item.nextToken());
			int weight = Integer.parseInt(item.nextToken());
			int amt = Integer.parseInt(item.nextToken());
			if (weight <= limit && amt > 0) {
				if (!byWeight.containsKey(weight)) {
					byWeight.put(weight, new ArrayList<>());
				}
				byWeight.get(weight).add(new int[] {value, amt});
			}
		}
 
		/*
		 * best[i][j] contiene el mayor valor que podemos
		 * obtener usando peso j y los primeros i tipos de peso
		 */
		long[][] best = new long[byWeight.size() + 1][limit + 1];
		for (long[] row : best) { Arrays.fill(row, Integer.MIN_VALUE); }
		best[0][0] = 0;
		int at = 1;
		for (var pair : byWeight.entrySet()) {
			int w = pair.getKey();
			ArrayList<int[]> items = pair.getValue();
			// ordenamos los ítems en orden inverso por valor
			items.sort(Comparator.comparingInt(i -> - i[0]));
			for (int i = 0; i <= limit; i++) {
				best[at][i] = best[at - 1][i];
				int copies = 0;
				int typeAt = 0;
				int currUsed = 0;
				long profit = 0;
				// recorremos tantos ítems como podamos hasta que nos quedemos sin ítems o
				// sin peso usable
				while ((copies + 1) * w <= i && typeAt < items.size()) {
					copies++;
					profit += items.get(typeAt)[0];
					if (best[at - 1][i - copies * w] != Integer.MIN_VALUE) {
						best[at][i] = Math.max(best[at][i],
						                       best[at - 1][i - copies * w] + profit);
					}
					currUsed++;
					if (currUsed == items.get(typeAt)[1]) {
						currUsed = 0;
						typeAt++;
					}
				}
			}
			at++;
		}
 
		long mostValue = 0;
		for (int i = 0; i <= limit; i++) {
			mostValue = Math.max(mostValue, best[byWeight.size()][i]);
		}
		System.out.println(mostValue);
	}
}