23/2/23学习记录（动态规划--背包九讲）

背包九讲问题

• 1. 01背包问题
• 2. 完全背包问题
• 3. 多重背包问题
• 4. 混合背包问题
• 5. 二维费用背包问题
• 6. 分组背包问题
• 7. 背包问题求方案数
• 8. 求背包问题的方案
• 9. 有依赖的背包问题

#include <stdio.h>

int relativelyPrime(int x, int y) {
    if (x == y && y == 1) {
        return 0;
    }
    int minn = x < y ? x : y;
    for (int i = 2; i <= minn; i++) {
        if (x % i == 0 && y % i == 0) {
            return 0;
        }
    }
    return 1;
}

void solution(int n, int m) {
    int count = 0;
    for (int a = n; a < m - 1; a++) {
        for (int b = a + 1; b < m; b++) {
            for (int c = b + 1; c < m + 1; c++) {
                if (relativelyPrime(a, b) &&
                    relativelyPrime(b, c) &&
                    relativelyPrime(a, c) &&
                    a * a + b * b == c * c) {
                    count++;
                    printf("%d %d %d\n", a, b, c);
                }
            }
        }
    }
    if (count == 0) {
        printf("Na\n");
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    solution(n, m);
    return 0;
}

2. 设置全局变量时存放在堆里，自动初始化。

3. 二维字符串数组排序

        int min;
        char tmp[11];
        if(k <= cnt) // sorting
        {
            for(i=0;i<k;i++) // k次简单排序
            {
                min = i;
                for(j=i+1;j<cnt;j++)
                {
                    if(strcmp(sort[min],sort[j])>0)
                    {
                        min = j;
                    }                   
                }
                if(min!=i)
                {
                    strcpy(tmp,sort[min]);
                    strcpy(sort[min],sort[i]);
                    strcpy(sort[i],tmp);
                }
            }
            printf("%s",sort[k-1]);
        }
    }