Atcoder解いてみた AtCoder Beginner Contest D - ナップサック問題

AtCoder Beginner Contest D - ナップサック問題

問題はこちら

回答

データ1

N<=30なため、完全な全探索だと、O(2^30)でO(10^9)となるため、半分全列挙を行う
半分全列挙だと、O(2^15 log(2^15))となり、かなり計算量を減らせる

データ2

重さが1000以下なため、重さを状態として用いて、ナップザックの重さがwの時の価値を最大化する

データ３

価値が1000以下なため、価値を状態として用いて、価値がvの時の重さを最小化する
つまり、重さに対する価値を最大化する

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>


int N, W;
std::vector<long long> VN;
std::vector<long long> WN;

std::vector<std::pair<long long, long long>> allPair(const std::vector<long long>& vin, const std::vector<long long>& win, bool isFirst) {
	std::vector<std::pair<long long, long long>> vecWV;

	// ビット全探索
	int n = vin.size();

	// 参考
	// https://drken1215.hatenablog.com/entry/2019/12/14/171657
	for (int bit = 0; bit < (1 << n); bit++) {
		std::pair<long long, long long> wv = { 0,0 };

		// bitの位置iに1が立っているか判定
		for (int i = 0; i < n; i++) {
			if (bit & (1 << i)) {
				wv.first += win[i];
				wv.second += vin[i];
			}
		}

		// 容量越えは無視
		if (wv.first > W) {
			continue;
		}

		vecWV.push_back(wv);
	}

	// 先に重さを低い順にソート
	std::sort(vecWV.begin(), vecWV.end());
	// vectorの1つ前の要素より、重いのに価値も低かったら入れない
	if (isFirst) {
		std::vector<std::pair<long long, long long>> vecWVRemoved;

		long long maxV = -1;
		for (const auto& [w, v] : vecWV) {
			// maxVを更新できたら追加
			if (v > maxV) {
				maxV = v;
				vecWVRemoved.push_back({ w,v });
			}
		}

		return vecWVRemoved;
	}
	else {
		return vecWV;
	}
}

// 半分全列挙
void solve1() {
	// N<=30なため、完全な全探索だと、O(2^30)でO(10^9)となるため、半分全列挙を行う

	// V, Wをに分割
	int fl = N / 2;

	std::vector<long long> Vf;
	std::vector<long long> Wf;

	std::vector<long long> Vs;
	std::vector<long long> Ws;

	for (int i = 0; i < N; i++) {
		if (i <= fl) {
			Vf.push_back(VN[i]);
			Wf.push_back(WN[i]);
		}
		else {
			Vs.push_back(VN[i]);
			Ws.push_back(WN[i]);
		}
	}

	// 1つ目の配列の全数列挙
	std::vector<std::pair<long long, long long>> vecPairF = allPair(Vf, Wf, true);
	std::vector<long long> vecWF;

	// 二分探索用に重さのみ抽出
	for (const auto& [w, v] : vecPairF) {
		vecWF.push_back(w);
	}

	// 2つ目の配列の全数列挙
	std::vector<std::pair<long long, long long>> vecPairS = allPair(Vs, Ws, false);

	long long ans = 0;
	for (const auto& [w, v] : vecPairS) {
		int wr = W - w; // 二分探索に使う値

		// 二分探索で、vecPairFからwr以下の要素を探す
		int idx = std::upper_bound(vecWF.begin(), vecWF.end(), wr) - vecWF.begin() - 1;
		ans = std::max(ans, v + vecPairF[idx].second);
	}

	std::cout << ans << std::endl;
}

// 重さが1000以下
// ナップザックの重さがwの時の価値を最大化する
void solve2() {
	std::vector<long long> dp(1000*200 + 1, 0);

	for (int i = 0; i < VN.size(); i++) {

		long long value = VN[i];
		long long weight = WN[i];
		// i番目の重さまでループ
		for (int w = W; w >= weight; w--) {
			//	重さwに至るにあたり、i番目の重さWN[i]のアイテムを入れるべきか、既存の重さwに対応する価値を採用するかどうか
			dp[w] = std::max(dp[w - weight] + value, dp[w]);
		}
	}

	long long ans = LLONG_MIN;
	for (int i = 0; i < dp.size(); i++) {
		ans = std::max(ans, dp[i]);
	}

	std::cout << ans << std::endl;
}

// 価値が1000以下
// 価値がvの時の重さを最小化する
// つまり、重さに対する価値を最大化する
void solve3() {
	long long vSum = 0;
	for (int i = 0; i < VN.size(); i++) {
		vSum += VN[i];
	}
	long long valMax = 1000 * 200;
	long long inf = (long long)200 * (long long)1000000010;
	std::vector<long long> dp(valMax + 1, inf);
	dp[0] = 0; // 価値0の場合、重さも0


	// ナップザックからとっていく方向にする?
	for (int i = 0; i < WN.size(); i++) {

		long long value = VN[i];
		long long weight = WN[i];
		// i番目の価値までループ
		for (int v = valMax; v >= value; v--) {
			//	価値vに至るにあたり、i番目の価値VN[i]のアイテムを入れるべきか、既存の価値vに対応する重さを採用するかどうか
			dp[v] = std::min(dp[v - value] + weight, dp[v]);
		}
	}

	long long ans = LLONG_MAX;

	// W以下の重さの中で、価値の最大値を取得
	for (int i = 0; i < dp.size(); i++) {
		if (dp[i] > W) {
			continue;
		}
		if (dp[i] == inf) {
			continue;
		}
		ans = i;
	}

	std::cout << ans << std::endl;
}

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> W;

	bool isdat1 = true;
	if (N > 30) {
		isdat1 = false;
	}

	bool isdat2 = true;
	bool isdat3 = true;
	for (int i = 0; i < N; i++) {
		int v, w;
		std::cin >> v >> w;

		VN.push_back(v);
		WN.push_back(w);

		if (isdat1) {
			isdat2 = false;
			isdat3 = false;
			continue;
		}

		if (w > 1000) {
			isdat2 = false;
		}
		if (v > 1000) {
			isdat3 = false;
		}
	}

	if (isdat1) {
		solve1();
	}
	else if (isdat2) {
		solve2();
	}
	else {
		solve3();
	}

	return 0;
}