算法练习-02

发表于 2020-10-11 更新于 2024-09-24 分类于 algorithms Waline：阅读次数：本文字数： 2.2k 阅读时长 ≈ 8 分钟

本文记录自己实践的算法相关练习，方便以后自己温故知新！

Problem-01 购物最少问题

小明最近往购物车中添加了N件商品，每件商品的价格是m₁…….m_n，0<N<1000, 0<m_i<=100，但是在结帐时发现超过自已的期望预算Y元，0<Y<10000，遂决定从购物车删除部分商品，从而没有超过预算，请帮助小明计算最多需要从购物车删除多少件商品？

[输入]

第一行的一个数字表示测试用例个数，接下来每两行表示具体的用例内容
用例的格式：
预算Y元  购物车里商品数量N
N件商品的价格（以空格为分界符）

[输出]

每一个用例对应的结果

[样例输入]

2
90 6
40 40 50 50 10 10
30 3
30 20 10

[样例输出]

4 #最多需要删除4件商品，比如分别删除一个50、40和两个10元商品
2 #最多需要删除2件商品，比如删除一个20和10元的商品

solution

本题的本质就是花Y元购买最少的商品数量，核心算法就是排序+贪心，先将N件商品从大到小的排序，然后以此迭代循环决定是否购买当前的商品，只要当前剩余的额度大于当前商品的价格，就选择购买。

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b)
{
	return (*(int *)b - *(int *)a);
}

int solve(int *array, int num, int budget)
{
	int count = 0, i = 0;
	
	for (i = 0; i < num; i++)
	{
		if (budget < array[i])
			continue;
		
		budget -= array[i];
		if(budget >= 0)
			count++;
	}
	
	return count;
}

int main(void)
{
	int m, i, j;
	int budget, num;
	int *price = NULL;
	while(scanf("%d", &m) != EOF)
	{
		for (i = 0; i < m; i++)
		{
			scanf("%d%d", &budget, &num);
			price = (int *)malloc(num*sizeof(int));
			for (j = 0; j < num; j++)
			{
				scanf("%d", price+j);
			}
			
			qsort(price, num, sizeof(int), compare);
			
			printf("%d\n", num - solve(price, num, budget));
			if (price)
			{
				free(price);
				price = NULL;
			}
		}
	}
	return 0;
}

Problem-02 购物最多问题

小明最近往购物车中添加了N件商品，每件商品的价格是m₁…….m_n，0<N<1000, 0<m_i<=100，但其预算只有Y元，0<Y<10000，请帮助小明计算最多能够从购物车购买多少件商品才不会超出预算？

[输入]

第一行的一个数字表示测试用例个数，接下来每两行表示具体的用例内容
用例的格式：
预算Y元  购物车里商品数量N
N件商品的价格（以空格为分界符）

[输出]

每一个用例对应的结果

[样例输入]

2
90 5
40 40 50 50 10
30 3
30 20 10

[样例输出]

3
2

solution

本题与上面那题看似一样，其本质是花Y元购买最多的商品数量，核心算法就是动态规划（DP）。本题实现使用了一维数组num来记录在当前预算下的最大购买数量，num[j]表示在预算为j的情况下最大购买商品数量，但对于第i件商品来说，它有存在两种状态，购买num[j-price[i]]+1，或者不购买num[j]，我们需要的是这两者中的较大的一个，即：num[j] = max(num[j],num[j-price[i]]+1)。与此题相似的题目是【动态规划入门】装箱问题

#include <stdio.h>
#include <string.h>

#define MAX(a,b)    ((a > b) ? a : b)

int num[10005];
int price[1000];

int main(void)
{
	int count, n, i, j, y, k;
	while(scanf("%d", &count) != EOF)
	{
		for (k = 0; k < count; k++)
		{
			memset(num, 0, sizeof(num));
			scanf("%d%d", &y, &n);

			for (i = 0; i < n; i++)
				scanf("%d", &price[i]);

			for (i = 0; i < n; i++)
			{
				for (j = y; j >= price[i]; j--)
				{
					num[j]=MAX(num[j], (num[j-price[i]]+1));
				}
			}

			printf("%d\n", num[y]);
		}
	}

	return 0;
}

Problem-03 序列排序

给定一个长度为N的序列，通过交换任意两个元素给序列重新排序，求需要的最少交换次数，就能将序列排列成递增的顺序，（序列中的元素互不重复）

[输入]

第一行测试用例个数，接下来每两行描述一个测试用例
用例的格式：
序列长度N
序列的各个元素a₁......a_n

[输出]

每一个用例需要的最少交换次数

[样例输入]

2
6
2 4 3 6 5 7
10
10 2 3 4 5 6 7 8 9 1

[样例输出]

2
1

solution

思路：构造“循环节”，原位置与排序后位置不一致的元素将至少需要一次交换。

图1 序列排序的图例

为了计算最少的交换次数，我们肯定希望一次交换将一个元素放入正确的位置，或者一次交换将两个元素都放入正确位置。如上图所示，循环节loop #1和loop #3都是一次交换就能够将两个元素放入正确位置，循环节loop #2每次交换只能将一个元素放入正确位置，所以其至少需要两次交换，循环节loop #4无需交换。我们可以推算出一个循环节至少需要的交换次数等于循环节内元素个数 - 1。
总结归纳，假设一个序列存在m个循环节，总交换次数=（loop#1内元素个数 - 1） + （loop#2内元素个数 - 1）+ … + （loop#m内元素个数 - 1） = 序列的长度 - m

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int solve(int *a, int len)
{
    int pos, i,loops = 0;
    /* 有序的序列 */
    int *b = (int *)malloc(len*sizeof(int));
    int *map, *flags;
    memcpy(b, a, len*sizeof(int));

    qsort(b, len, sizeof(int), compare);

    map = (int *)malloc((b[len-1]+1)*sizeof(int));
    for(pos = 0; pos < len; pos++)
        map[b[pos]] = pos;	/* 记录每个元素应该放入的位置 */

    flags = (int *)malloc(len*sizeof(int));	/* 标记元素是否被访问过 */
    memset(flags, 0, len*sizeof(int));

    for (pos = 0; pos < len; pos++)
    {
        if (!flags[pos])
        {
            i = pos;
            while(!flags[i])	/* 构造循环节 */
            {
                flags[i] = 1;
                i = map[a[i]];	/* 原序列中i位置的元素在有序序列中的位置 */
            }
            loops++;	/* 循环节计数 */
        }
    }

    if (b)
        free(b);

    if (map)
        free(map);

    if (flags)
        free(flags);

    return len - loops;
}

int main()
{
    int m;
    int n, i;
    int *array;

    while(scanf("%d", &m) != EOF)
    {
        while(m--)
        {
            scanf("%d", &n);
            array = (int *)malloc(n*sizeof(int));
            memset(array, 0, n*sizeof(int));
            for(i = 0; i < n; i++)
                scanf("%d", array+i);

            printf("%d\n", solve(array, n));

            if (array)
            {
                free(array);
                array = NULL;
            }
        }
    }
}

如果题目稍微修改一下：将任意两个元素交换改成相邻两个元素交换，结果就变成求序列的逆序对数，可以借鉴参考小朋友排列和归并排序（逆序对的解决）

Problem-04 找数字

从一个n位数中选出m位按原来顺序组成新的数字并使其最大。（n, m < 100）

[输入]

第一行测试用例个数，接下来每一行描述一个测试用例
用例的格式：
位数n m 一个位数为n的数字

[输出]

每一个用例得到的最大数字

[样例输入]

2
7 3 9123487
5 2 51234

[样例输出]

987
54

solution

最优解法应该是贪心法，能够边输入边处理，由于需要选出m个数字，即删除n-m个数字。假设变量i表示遍历到输入的第i个数字（从0开始），那么待输入的数字还有n-i个需要遍历。变量k表示第k个已经选中的数字，只有当k<m时才能继续挑选数字。若k+(n-i)>m，即已选出的数字个数加上等待遍历的数字个数大于要选出的位数时，需要用后面较大的数替换前面已经选出的数字，此处的贪心策略是：设当前输入的数是c，通过k从已选出数字中向前寻找恰好大于c的那个数字所对应的位置p，然后替换掉第p+1位的数字，这种策略可以保证所选出的m位数字的结果是最大的。参考UVa11491- Erasing and Winning（从一题看多解）和习题8-4 奖品的价值 UVa11491

#include <stdio.h>
#include <string.h>

char a[105];

int main()
{
    int count;
    int n, m, i, k;
    char c;
    while(scanf("%d", &count) != EOF)
    {
        while(count--)
        {
            memset(a, 0, sizeof(char)*105);
            scanf("%d%d", &n, &m);
            getchar();

            k = 0;
            for(i = 0; i < n; i++)
            {
                c = getchar();
                /* 需选出m个数字， 已选中到第k个数字， 还有n-i个未遍历，若k+(n-i) > m，
                 * 说明若后面有比前面选中数字大的，还需要替换掉， 此时选择替换掉小于c的数字
                 */
                while(k > 0 && (i - k < (n - m)) && a[k] < c)
                    k--;
                if (k  < m)
                    a[++k] = c;	/* 若k<m，说明还没有选够m个数字 */
            }
            a[++k] = '\0';
            printf("%s\n", a + 1);
        }
    }
    return 0;
}

本题解法也适用从一个n位数字中删除d个数字，使剩下数字最大。