216 - Getting in Line

Problem Link

#include<bits/stdc++.h>
using namespace std;
#define MAX 10

int n;
vector<int>path;
double dist[MAX][MAX];

double TSP()
{
    vector<int>vertex;
    for(int i = 1; i <= n; i++)
            vertex.push_back(i);
    double min_path = numeric_limits<double>::max();

    do
    {
        double curr_pathweight = 0.0;
        for(int i = 0; i < vertex.size(); i++)
        {
            curr_pathweight += dist[vertex[i]][vertex[i+1]];
        }
        if(min_path > curr_pathweight)
        {
            min_path = curr_pathweight;
            path = vertex;
        }
    }
    while(next_permutation(vertex.begin(), vertex.end()));

    return min_path;
}


int main()
{
    int test = 0;
    while(cin>>n && n)
    {
        memset(dist, 0.0, sizeof(dist));
        double x[10], y[10];
        for(int i = 1; i <= n; i++)
            cin>>x[i]>>y[i];
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dist[i][j] = sqrt(((x[i]-x[j]) * (x[i] - x[j])) + ((y[i] - y[j]) * (y[i] - y[j]))) + 16.00;
            }
        }
        cout<<"**********************************************************"<<endl;
        cout<<"Network #"<< ++test<<endl;
        double ans = TSP();
        for(int i = 0; i < path.size()-1; i++)
        {
            int pin = path[i];
            int pin1 = path[i+1];
            cout<<fixed<<setprecision(2)<<"Cable requirement to connect ("<<(int)x[pin]<<","<<(int)y[pin]<<") to ("<<(int)x[pin1]<<","<<(int)y[pin1]<<") is "<<dist[pin][pin1]<<" feet."<<endl;
        }
        cout<<fixed<<setprecision(2)<<"Number of feet of cable required is "<<ans<<"."<<endl;
    }

    return 0;
} 

674 - Coin Change

Problem link

It is a classical problem of Coin change problem.
In this problem test case number has no limit(>10^7). So, if you call recursion function for each test case it must get WA. To get ride off this problem you have to do pre-calculation and store answer in a array.

My Code is given below:

#include<bits/stdc++.h>
using namespace std;

int A[] = {1,5,10,25,50};
int table[7490];

void coin_change()
{
    memset(table,0,sizeof(table));

    table[0] = 1;

    for(int i = 0; i < 5; i++)
        for(int j = A[i]; j <= 7489; j++)
            table[j] += table[j-A[i]];
}

int main()
{
    int make;
    coin_change();
    while(cin>>make)
    {
        cout<<table[make]<<endl;
    }

    return 0;
}

10130 - SuperSale

Problem Link

This is a classical 0-1 Knapsack Problem.
To solve this problem please read this first.

Now, first try by yourself.
If you get any difficulty , you can get help from my solution...

//Time Complexity O(item * bag_weight * G)
#include<bits/stdc++.h>
using namespace std;

int weight[10000], value[10000];

int knapsack(int bag_weight, int item)
{
    int K[item+1][bag_weight+1];
    for(int i = 0; i <= item; i++)
    {
        for(int w = 0; w <= bag_weight; w++)
        {
            if(i==0 || w==0)
                K[i][w] = 0;
            else if(weight[i-1]<=w)
                K[i][w] = max(K[i-1][w], K[i-1][w-weight[i-1]]+value[i-1]);
            else
                K[i][w] = K[i-1][w];
        }
    }

    return K[item][bag_weight];
}

int main()
{
    int T;
    cin>>T;
    for(int t = 0; t < T; t++)
    {
        int A[31] = {0}, sum = 0;
        int n;
        cin>>n;
        for(int i = 0; i < n; i++)
            cin>>value[i]>>weight[i];
        int G, MG;
        cin>>G;
        for(int i = 0; i < G; i++)
        {
            cin>>MG;
            if(A[MG]==0)
                A[MG] = knapsack(MG,n);
            sum+=A[MG];
        }
        cout<<sum<<endl;
    }
    return 0;
}