Subset Sum Problem

The problem is this: given a set of integers, does the sum of some non-empty subset equal exactly zero?The problem is NP-Complete. wiki

An equivalent problem is this: given a set of integers and an integer s, does any non-empty subset sum to s? Subset sum can also be thought of as a special case of the knapsack problem. One interesting special case of subset sum is the partition problem, in which s is half of the sum of all elements in the set.

topCoder: PayBill Editorial

There are two basic approaches to this problem. The first, which inevitably fails due to timeout on larger test cases, is to try obtain the sum by either including or excluding the first element, and then calling itself recursively with the remainder of the set. Unfortunately, with the maximum 50 people, this is over 1 quadrillion operations to perform.

Instead, a more clever, dynamic programming approach needs to be used. Since each item can only be up to 10,000, we know that the sum cannot be more than 500,000. So, we simply need a boolean array of 500,000 elements, where the i-th element represents whether or not we can reach the total i with some subset of the original values. In code it looks something like this:

boolean[] canTotal = new boolean[500001];
canTotal[0] = true;
for (int i = 0; i < meals.length; i++)
  for (int j = totalMoney; j >= meals[i]; j--)
     if (canTotal[j - meals[i]]) canTotal[j] = true;

topCoder: LoadBalancing Editorial

int minTime(vector<int> chunkSizes)
{
   vector<int> dp(204801, 0);
   dp[0] = 1;
   int total = 0;
   for (int i=0; i<(int)chunkSizes.size(); i++)
   {
       total += chunkSizes[i]/1024;
       for (int j=204800; j>=0; j--)
           if (dp[j] == 1)
               dp[j+chunkSizes[i]/1024] = 1;
   }
   for (int i=(total+1)/2; true; i++)
       if (dp[i] == 1)
           return 1024 * i;
}

UVa 562: Dividing Coins

跟上面一题如出一辙，就是平分问题。这里用了bitvector

const int MAX = 50000;
const unsigned int N = 1563;
unsigned int a[N+1];

int coin[101];
int main() {
    int ndata;
    scanf("%d ", &ndata);
    while(ndata--) {
        int n; 
        scanf("%d ", &n);

        for(int i = 0; i < n; ++i) {
            scanf("%d ", &coin[i]);
        }

        int total = std::accumulate(coin, coin+n, 0);

        memset(a, 0, sizeof(int)*(total>>SHIFT));
        SET(a, 0);
        for(int i = 0; i < n; ++i) {
            for(int j = total; j >= 0; --j)
                if(TEST(a, j))
                    SET(a, j+coin[i]);
        }

        for(int i = (total+1)/2; true; ++i) {
            if(TEST(a, i)) {
                printf("%d\n", abs(2*i-total));
                break;
            }
        }
    }

}

UVa 11517 Exact Change

这道要多记一个coin的数目，不能用bitvector了

        a[0] = 1;
        for(int i = 0; i < n; ++i) {
            for(int j = max-1; j >= 0; --j)
                if(a[j]) {
                    int t = j+ bill[i];
                    if(t > max) continue;
                    if(a[t] != 0)
                        a[t] = a[t] < a[j]+1 ? a[t]: a[j]+1;
                    else 
                        a[t] = a[j]+1;
                }
        }
        for(int i = price; i <= MAX; ++i) {
            if(a[i]) {
                printf("%d %d\n", i, a[i]-1);
                break;
            }
        }