Ronzii's Blog

Just your average geek's blog

Prime Subsets

Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number.
Algorithm

  1. Generate prime numbers using sieve of eratosthenes (O(n^2))
  2. Generate all subsets using 0-1 Knapsack i.e this helps determine the number of ways it is possible get the value i, input ranging from 1 to n. The general complexity of 0-1 Knapsack is O(nK) where K is the sum of all elements in the vector. Since there are numbers ranging from 1 to n i.e sum is n(n-1)/2. The overall complexity becomes O(n^3)
  3. Iterate all subsets which are prime. O(K)
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#define SIZE 1000
#define MAX (int)(SIZE-3)/2
using namespace std;
unsigned long long primes[MAX+1];
bitset<MAX+1> bset;
void setPrimes()
{
    unsigned long long i,j;
    for(i=0; i*i<=SIZE; i++)
        if(!bset.test(i))
            for(j=i+1; (2*j+1)*(2*i+3)<=SIZE; j++)
                bset.set(((2*j+1)*(2*i+3)-3)/2);
    primes[0]=2;
    for(i=1,j=0; j<MAX+1; j++)
        if(!bset.test(j))
            primes[i++]=2*j+3;
}
int knapsack(int n)
{
    vector<int> v;
    for(int i=1; i<=n; i++)
        v.push_back(i);
    int sum = accumulate(v.begin(),v.end(),0);
    int *s = new int[sum];
    for(int i=0; i<sum; i++) s[i] = 0;
    s[0] = 1;
    for(int i=0; i<v.size(); i++)
    {
        for(int j = sum-v[i]; j>=0; j--)
        {
            if(s[j])
            {
                s[j+v[i]]+=1;
            }
        }
    }
    int total = 0;
    for(int i=0; i<n; i++)
    {
        cout<<primes[i]<<" "<<s[primes[i]]<<endl;
        total+=s[primes[i]];
    }
    return total;
}
int main()
{
    setPrimes();
    cout<<knapsack(10);
    return 0;
}

March 26, 2012 Posted by | C++, Dynamic Programming | , , , , , | 2 Comments

0-1 Knapsack Problem

#include<iostream>
#include<cstring>
using namespace std;
int knapSack(int W, int wt[], int val[], int n)
{
    int K[n+1][W+1];
    for(int w=0; w<=W; w++)
    {
        for(int i=0; i<=n; i++)
        {
            if(i==0||w==0) K[i][w] = 0;
            // Weight is more than Knapsack capacity, then skip it
            else if(wt[i-1]>w)
            {
                K[i][w] = K[i-1][w];
            }
            // Weight is inside Knapsack capacity, Calculate maximum possible weight
            // by comparing the maximum till now and the new weight
            else
            {
                K[i][w] = max(K[i-1][w],val[i-1]+K[i-1][w-wt[i-1]]);
            }
            cout<<K[i][w]<<" ";
        }
        cout<<endl;
    }
    return K[n][W];
}
int main()
{
    int value[] = {20,30,10,50};
    int weight[] = {5,3,1,2};
    int  W = 8;
    int n = sizeof(value)/sizeof(value[0]);
    cout<<knapSack(W, weight, value, n);
    return 0;
}

March 19, 2012 Posted by | C++, Dynamic Programming | , , , | Leave a comment