BoatBurglary - ACM Exercice 내가 <a href="http://acm.tju.edu.cn/toj/showp4095.html" rel="nofollow">this problem</a>을하려고

Question

:

라시드는 보트에 살고, 단지 몇 가지 항목을 소유, n은 정확하게 할 수 있습니다. 그는 자신의 아이템을 중요하게 취급하고, 각각의 무게를 높은 정확도로 측정했습니다. 항목 i는 Wi 마이크로 그램의 무게입니다. 어느 날 밤 도둑이 보트를 찾아 일부 물건을 훔친다. Rachid는 배가 더 가볍기 때문에 다음날 아침 을 알게되고 에서이 차이가 D 마이크로 그램 인 수위를 측정 할 수있었습니다. 그는 에 얼마나 많은 항목이 누락되었는지 알고 싶습니다.이 가중치를 검토하여 에게 도움을 요청합니다.

입력 입력의 첫 줄 시험 건수 구성

, T. T 테스트 케이스가 따른다. 각각의 경우는 두 줄로 구성되며 첫 번째는 두 개의 정수 N과 D가 공백으로 구분되어 포함됩니다. 그런 다음 두 번째 줄에는 모든 항목의 가중치를 나타내는 n 개의 정수가 포함되며 은 공백으로 구분됩니다. X는 케이스 번호 (1에서 시작하는)이며, 각각의 테스트 케이스 출력 함유 한 선 "Y 케이스 #x를"를 OUPUT

. 누락 된 품목 수인 을 결정할 수 있다면 y는이 번호입니다. 문제에 대한 대답이 y 인 경우 "AMBIGIOUS"문자열이고 답변이없는 경우 "IMPOSSIBLE"문자열입니다 (명확하게하기 위해 인용 부호가 추가되어 있으며 은 출력의 일부가 아닙니다).

Limits 

1<=T<=20 
1<=N<=30 
0<=Wi<=10^9 

나는이 고전 부분적인 문제는 우리가 D. NP의 부분 집합 문제와 같은 그 합을 얼마나 많은 부분 집합 발견해야한다, 즉,라고 처음에는 생각, 그래서이 상황에 정말 적용하지 않습니다.

이 문제를 어떻게 해결할 수 있는지 알고 계십니까?

Answer 1

최대 두 개의 더미로 항목을 나눕니다. 각 더미의 각 하위 세트의 크기를 찾습니다. 두 번째 더미의 모든 하위 집합을 크기로 인덱싱 된 해시 테이블에 넣고 첫 번째 더미의 각 하위 집합에 대해 올바른 가중치가 있는지 확인하기 위해 해시 테이블을 조사합니다.

Answer 2

감사 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; 
} 

당신이