Кража со взломом — упражнение ACM
Я пытаюсь сделать Эта проблема:
Рашид живет на лодке и владеет всего несколькими предметами, если быть точным.
Он очень заботится о своих вещах и измеряет вес каждого из
их с высокой точностью. Элемент I весит Wi микрограмм. Одна ночь
Вор посещает свою лодку и воровывает некоторые предметы. Рашид замечает, что
на следующее утро, потому что лодка легче, и он мог измерить от
уровень воды, что эта разница составляет D микрограмм. Он хотел бы
узнать, сколько предметов не хватает, просто изучив эти веса, и
просит вас о помощи.вход
Первая строка ввода содержит количество тестовых случаев, за которыми следуют тесты T. Каждый случай состоит из двух строк, первая
содержит два целых числа N и D, разделенных пробелом. Потом второй
строка содержит n целых чисел, представляющих веса всех предметов,
разделены пробелом.Ouput
Для каждого тестового случая выведите одну строку, содержащую «Case #x: y», где x — номер случая (начиная с 1). Если количество пропущенных предметов
можно определить, то у это число. Если есть несколько
ответы на проблему у это строка «AMBIGIOUS», и если нет
ответ у — строка «НЕВОЗМОЖНО» (цитаты добавлены для ясности и
не часть вывода).Limits 1<=T<=20 1<=N<=30 0<=Wi<=10^9
Сначала я подумал, что это классическая проблема подмножеств, т.е. мы должны найти, сколько подмножеств имеют их сумму, равную D. Задача подмножеств в NP, так что она не очень применима к этой ситуации.
У вас есть идеи о том, как я могу решить эту проблему?
Решение
Разделите предметы на две стопки не более 15. Определите размер каждого подмножества каждой стопки. Поместите все подмножества второй стопки в хеш-таблицу, проиндексированную по размеру, и для каждого подмножества первой стопки посмотрите в хеш-таблицу, чтобы увидеть, есть ли что-то с правильным весом.
Другие решения
Благодаря tmyklebu, вот мой код:
#include <fstream>
#include <cstdio>
#include <string.h>
#include <iostream>
#include <sstream>
#include <map>
#include <bitset>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define CLR(T, V) memset(T, V, sizeof T)
typedef unsigned long long u;
/* ---------------------- BEGIN ----------------------- */
const int NN = 100;
int W[NN];int count_bits(int i) {
int c;
for (c = 0; i; c++)
i &= i - 1; // clear the least significant bit set
return c;
}
u sum_subset(int S, int offset=0) {
bitset<64> bs(S);
u sum = 0;
FOR(i, 0, 64)
if (bs[i]) sum += W[offset + i];
return sum;
}
string int_to_string(int i) {
ostringstream stream;
stream << i;
return stream.str();
}
string solve(int N, int D) {
map<u, int> sum;
map<u, int> nb_arg_sum;
int pile_size = (N+1) / 2;
int nb_subsets = 1 << pile_size;
FOR(i, 0, nb_subsets) {
u s = sum_subset(i);map<u, int>::iterator it = sum.find(s);
if (it == sum.end())
nb_arg_sum[s] = 1;
else if(nb_arg_sum[s] == 1) {
nb_arg_sum[s] = 2 - (count_bits(i) == count_bits(it->second));
}
sum[s] = i;
}
int nb_sol = 0;
int sol = - 1;
nb_subsets = 1 << (N - pile_size);
FOR(i, 0, nb_subsets) {
u s = sum_subset(i, pile_size);
map<u, int>::iterator it = sum.find(D - s);
if (it != sum.end()) {
int sol2 = count_bits(i) + count_bits(it->second);
if ( (sol >= 0 && sol != sol2) || nb_arg_sum[D - s] > 1) return "AMBIGIOUS";
sol = sol2;
}
}
return (sol >= 0) ? int_to_string(sol) : "IMPOSSIBLE";
}
int main() {
#ifndef ONLINE_JUDGE
ifstream input("input.txt");
#define cin input
#endif
int T; cin >> T;
FOR(i, 0, T) {
CLR(W, 0);
int N, D;
cin >> N >> D;
FOR(j, 0, N) cin >> W[j];
cout << "Case #" << i + 1 << ": " << solve(N, D) << endl;
}
#ifndef ONLINE_JUDGE
system("pause");
#endif
return 0;
}
Скажи мне, что ты думаешь