제출 #1255808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255808		cybergiest	Knapsack (NOI18_knapsack)	C++20	100 / 100	65 ms	33096 KiB

knapsack

// Problem: Minimizing Coins
// Contest: CSES - CSES Problem Set
// URL: https://cses.fi/problemset/task/1634
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
#define V vector
#define P pair
#define pb push_back
#define epb emplace_back
#define endll "\n"
 
namespace config {
	void io() {
		ios::sync_with_stdio(false);
	    cin.tie(nullptr);
	}
}

namespace oldsolution {
	void main() {
		// we cant literally just push back every single copy for all K for an item
		// try to group them together?
		// no but then it might lead to innacurate knapsack logic later
		// bundle with binary decomposition?
		// so weight 13 = 1 + 4 + 8
		
		int weightLimit, n;
		cin >> weightLimit >> n;
		V<int> weights, values;
		for (int i = 0; i < n; i++) {
			int value, weight, quantity;
			cin >> value >> weight >> quantity;
			int power = 1;
			while (quantity > 0) {
				int chunk = min(power, quantity);
				quantity -= chunk;
				int newWeight = weight * chunk;
				int newValue = value * chunk;
				weights.pb(newWeight);
				values.pb(newValue);
				power <<= 1;
			}
		}
		
		// ok so now this is just a classical 0/1 knapsack
		
		// dp[i] is the most value for a certain weight limit i
		
		V<int> dp(weightLimit + 1, 0);
		
		// base case:
		// the most value for a weight limit of 0 would be 0
		// this is already there since I initialized the whole vector to 0s
		
		// outside loop: iterate over items
		const int numItems = weights.size();
		for (int item = 0; item < numItems; item++) {
			for (int currentWeightLimit = weightLimit; currentWeightLimit >= weights[item]; currentWeightLimit--) {
				dp[currentWeightLimit] = max(dp[currentWeightLimit], dp[currentWeightLimit - weights[item]] + values[item]);
			}
		}
		
		cout << dp[weightLimit] << endll;
		
		// THIS SOLUTION DID NOT WORK BECAUSE OF RUNTIME ERRORS, BUT IT WAS PARTIALLY RIGHT
	}
}

namespace solution {
	void main() {
		int weightLimit, n;
		cin >> weightLimit >> n;
		map<int, V<P<int, int>>> itemsByWeight; // <weight, <value, quantity>>
		for (int i = 0; i < n; i++) {
			int value, weight, quantity;
			cin >> value >> weight >> quantity;
			if (weight <= weightLimit) {
				itemsByWeight[weight].epb(value, quantity);
			}
		}
		// sort in descending order
		for (auto& [weight, items] : itemsByWeight) {
			sort(items.begin(), items.end(), [](const P<int, int>& a, const P<int, int>& b) {
				return a.first > b.first;
			});
		}
		
		V<V<int64>> dp(itemsByWeight.size() + 1, V<int64>(weightLimit + 1, INT32_MIN));
		// dp[i][j]
		// i -> groups processed so far : [0, num of groups]
		// j -> current total weight limit : [0, weight limit]
		dp[0][0] = 0;
		
		int groupIndex = 1;
		for (auto& [weight, items] : itemsByWeight) {
			// already sorted in decreasing order
			for (int cap = 0; cap <= weightLimit; cap++) { // its 2D dp so yes were going up
				// dont take anything from this weight grp
				dp[groupIndex][cap] = dp[groupIndex - 1][cap];
				
				// take some items from this weight grp
				int64 totalValue = 0;
				int copies = 0;
				int typeIndex = 0; // index in items vector
				int usedFromType = 0; // for the current (val, quantity)
				
				while ((copies + 1) * weight <= cap && typeIndex < items.size()) {
					copies++;
					// add this items value
					totalValue += items[typeIndex].first;
					if (dp[groupIndex - 1][cap - copies * weight] != INT32_MIN) {
						dp[groupIndex][cap] = max(dp[groupIndex][cap], dp[groupIndex - 1][cap - copies * weight] + totalValue);
					}
					
					usedFromType++;
					if (usedFromType == items[typeIndex].second) { // if I've used up all of the copies for this guy
						usedFromType = 0;
						typeIndex++;
					}
				}
			}
			
			groupIndex++;
		}
		int64 ans = 0;
		for (int cap = 0; cap <= weightLimit; cap++) {
				ans = max(ans, dp[groupIndex - 1][cap]);
		}
		cout << ans << endll;
	}
}

int main() {
	config::io();
	solution::main();
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27