algorithm期末考试

简单背包问题

#include <iostream>

using namespace std;
int data[100];

int weight(int w, int n)//w是重量，n是剩下的件数
{
    if (w == 0) {
        return 1;
    }
    if (w!=0&&n == 0) {
        return 0;
    }
    if (weight(w - data[n], n - 1)) {
        return 1;
    } else {
        return weight(w, n - 1);
    }
}

int main() {
    int w, n;
    while (cin>>w>>n) {
        for (int i = 1; i <= n; i++) {
            cin >> data[i];
        }
        if (weight(w, n)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

Buyer

/*
输入1：可以支配的钱和可以选择的物品种类数
输入2：N行，每行为每种物品的价钱和受欢迎程度
输出1：可能达到的最大的受欢迎程度
输出2：购买的物品的编号（物品不重复购买）
 */
#include <iostream>

using namespace std;
typedef struct Food {
    int m_money;
    int m_value;
} Food;
Food food[1000];
int F[1000][1000] = {0};

int maxlove(int n, int money) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= money; j++) {
            if ((j - food[i].m_money) >= 0) {
                F[i][j] = max(F[i - 1][j], F[i - 1][j - food[i].m_money] + food[i].m_value);
            } else {
                F[i][j] = F[i - 1][j];
            }
        }
    }
    return F[n][money];
}

int main() {
    int money, n;
    while (cin >> money >> n) {
        food[0].m_money = 0;
        food[0].m_value = 0;
        for (int i = n; i >= 1; i--) {
            cin >> food[i].m_money >> food[i].m_value;
        }
        int result=maxlove(n,money);
        cout << result << endl;//n是种类总数,money是钱
        if(result==0)
            continue;
        int remain = money;
        int flag=0;
        for (int i = n; i >= 1; i--) {
            if (remain >= food[i].m_money) {
                if (F[i][remain] - F[i - 1][remain - food[i].m_money] == food[i].m_value) {
                    remain = remain - food[i].m_money;
                    if(flag==0)
                    {
                        cout << n - i + 1;
                        flag=1;
                    }
                    else
                        cout <<" "<< n - i + 1;
                }
            }
        }
        cout<<endl;
    }
}

Renting Boats

#include<iostream>
/*
 假设输入数据为：
                  4
            5 14 23
               5 12
                  8
以下为输入的数据分布（即m[i][j]）
    租船点\还船点
                0   1   2   3
            0   0   5   14  23
            1   0   0   5   12
            2   0   0   0   8
            3   0   0   0   0
p[i][j]：
    租船点\还船点
                0   1   2   3
            0   0   5   10  17
            1   0   0   5   12
            2   0   0   0   8
            3   0   0   0   0
 */
using namespace std;


int main() {
    int n;
    cin >> n;
    int m[200][200] = {0};
    int p[200][200] = {0};
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cin >> m[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        int minNum = m[0][i];
        for (int j = 0; j < i; j++) {
            minNum = min(minNum, p[0][j] + m[j][i]);
        }
        p[0][i] = minNum;
    }
    cout << p[0][n - 1]<<endl;
}

Shortest path counting

#include <iostream>
using namespace std;
int P[100][100];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        P[0][i]=1;
        P[i][0]=1;
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=n;j++){
            P[i][j]=P[i-1][j]+P[i][j-1];
        }
    }
    cout<<P[n-1][n-1]<<endl;
}

Coin-collecting by robot

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int map[1000][1000]={0};
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>map[i][j];
    for(int i=1;i<m;i++){
        map[0][i]=map[0][i-1]+map[0][i];
    }
    for(int i=1;i<n;i++){
        map[i][0]=map[i-1][0]+map[i][0];
    }
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            map[i][j]=max(map[i-1][j],map[i][j-1])+map[i][j];
    cout<<map[n-1][m-1];
    cout<<"\r\n";
}

Soldiers

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n,x[10001],y[10001];
    int xs,ys;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>x[i]>>y[i];
        }
        sort(x,x+n);
        sort(y,y+n);
        for(int i=0;i<n;i++){
            x[i]-=i;
        }
        sort(x,x+n);
        xs=ys=0;
        for(int i=0;i<n;i++){
            xs+=abs(x[i]-x[n/2]);
            ys+=abs(y[i]-y[n/2]);
        }
        cout<<xs+ys<<endl;
    }
}

Independent Task Scheduling

#include <iostream>

using namespace std;
int dp[202][10000];//dp[i][j] 表示前i个作业中A机器花j分钟的时候 B机器所花时间
int main() {
    int n;
    cin >> n;
    int a[200], b[200];
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= sum; j++) {
            if (j < a[i]) {//A机器时间不足，只能用B的
                dp[i][j] = dp[i - 1][j] + b[i];
            } else {
                //dp[i][j] = dp[i-1][j]+b[i]代表第i个任务交给B来做，所以做完前i个任务的时候,A机器和前i - 1的任务一样，还是花了j分钟，而B机器则花dp[i-1][j]+b[i]分钟；
                //dp[i][j] = dp[i-1][j-a[i]]代表第i个任务交给A来做，现在的A机器花费时间是j，所以在前i - 1个任务完成的时候，A机器是花了j-a[i]分钟的，所以现在B机器还是花了dp[i-1][j-a[i]]分钟；
                dp[i][j] = min(dp[i - 1][j] + b[i], dp[i - 1][j - a[i]]);
            }
        }
    }
    int ans = 999999;
    //max(dp[n][i],i) 表示完成前n个作业A机器花i分钟 B机器花dp[n][i]分钟情况下，最迟完工时间
    for (int i = 0; i <= sum; i++)
        ans = min(ans, max(dp[n][i], i));
    cout << ans << endl;
    return 0;
}

Arbitrage

#include <iostream>
#include <map>

using namespace std;
map<string, int> money;
double rates[100][100];
int n;

int Arbitrage() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                double tmp = rates[i][k] * rates[k][j];
                rates[i][j] = max(tmp, rates[i][j]);
                if (rates[i][j] * rates[j][i] > 1) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    int flag = 0, countt = 1;
    while (cin >> n && n) {
        for (int i = 0; i < n; i++) {
            string temp;
            cin >> temp;
            money[temp] = i;
            rates[i][i] = 1;
        }
        int m;
        cin >> m;
        for (int i = 0; i < m; i++) {
            string a, b;
            double rate;
            cin >> a >> rate >> b;
            rates[money[a]][money[b]] = rate;
        }
        flag = Arbitrage();
        if (flag)
            cout << "Case " << countt++ << " Yes" << endl;
        else
            cout << "Case " << countt++ << " No" << endl;

    }
    return 0;
}

求最小生成树(Prim算法）

#include<iostream>
#include<cstring>
#define inf 32767

using namespace std;

typedef struct {
    int n;
    int e;
    char data[500];
    int edge[500][500];
} Graph;

typedef struct {
    int index;
    int cost;
} mincost;

typedef struct {
    int x;
    int y;
    int weight;
} EDGE;


typedef struct {
    int index;
    int flag;
} F;

void create(Graph &G, int n, int e) {
    int i, j, k, w;
    char a, b;
    for (i = 0; i < n; i++)
        cin >> G.data[i];
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            if (i == j)
                G.edge[i][j] = 0;
            else
                G.edge[i][j] = inf;//模板里是G.edge[i][j]=100;
        }

    for (k = 0; k < e; k++) {
        cin >> a;
        cin >> b;
        cin >> w;
        for (i = 0; i < n; i++)
            if (G.data[i] == a) break;
        for (j = 0; j < n; j++)
            if (G.data[j] == b) break;

        G.edge[i][j] = w;
        G.edge[j][i] = w;
    }
    G.n = n;
    G.e = e;
}


void Prim(Graph &G, int v) {
    int lowcost[100];
    int min, closest[100], i, j, k;
    for (i = 0; i < G.n; i++) {
        lowcost[i] = G.edge[v][i];
        closest[i] = v;
    }
    for (i = 1; i < G.n; i++) {
        min = inf;
        for (j = 0; j < G.n; j++) {
            if (lowcost[j] && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        cout << '(' << G.data[closest[k]] << ',' << G.data[k] << ')';
        lowcost[k] = 0;
        for (j = 0; j < G.n; j++)
            if (G.edge[k][j] && G.edge[k][j] < lowcost[j]) {
                lowcost[j] = G.edge[k][j];//更新距离
                closest[j] = k;
            }
    }
}


int main() {
    Graph my;
    int n, e;
    cin >> n >> e;
    create(my, n, e);
    Prim(my, 0);
    return 0;
}