最大乘积问题+0-1背包问题+矩形分割算法

最大乘积问题

问题描述：

? 设n是一个正整数，现在要求将n分解为若干个互不相同的自然数的和，并且使这些自然数的乘积最大，对于给定的正整数n，计算最优分解方案。

? 提示：

把一个正整数从中间分开（如果是偶数直接除以2如果是奇数，分别加1除以2，减1除以2）
其中一部分保留在A[]数组中（奇数的话，比较大的那一部分保留给A[]数组），另一部分赋给temp，并重复1，2 步骤
最后把temp赋给A[]数组

C语言：贪心算法

#include <stdio.h>
#define MAX 100

int main(){
    int n;
    int a[MAX];
    printf("输入正整数n：");
    scanf("%d",&n);
    int x=2;
    int index=0;
    a[index++]=x;
    n-=x;
    //将n分解放进数组
    while(n>a[index-1]){
        a[index]=a[index-1]+1;
        n-=a[index];
        index++;
    }
    int num=index-1;
    //将余量加入从后向前分成1加入数组
    while(n){
        a[num]++;
        num=(num-1+index)%(index);
        n--;
    }
    
    //计算最大乘积
    int result=1;
    printf("\n划分的各个数：");
    for(int i=0;i<index;i++){
        printf("%d ",a[i]);
        result*=a[i];
     }
     printf("\n\n最大乘积为：%d\n",result);
    
    return 0;
 }

来自：https://blog.csdn.net/qq_41596568/article/details/93398496

0-1背包问题

问题描述：

? 给定n种物品和一个容量为M的背包，第i个物品的重量为w****i，效益值为p****i，假设该问题的解向量为(x1, x2, … , x****n)，其中，若x****i=1表示第i个物品放在包中；若x****i=0表示第i个物品没有被选中，i=1, 2, … , n。要求依据动态规划思想构造一个装包算法，使得背包的总效益值达到最大，并加以实现。

? 极大化函数:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F1A31wSr-1636811286516)(/Users/xinyu/Library/Application Support/typora-user-images/image-20211112221513189.png)]达到极大。

? 约束条件：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Y80O4UAI-1636811286526)(/Users/xinyu/Library/Application Support/typora-user-images/image-20211112221637402.png)]xi=0 或xi=1。

? 假设n=20，M小于20个物品的总重量。随机生成(w****i, p****i)，每个w****i和p****i均为正整数，i=1, 2, … , n。输入数据用文件保存，以便打印输出。

? 输出生成的输入数据及根据输入数据所得到的解，并说明所得到的解是否为最优解。

C语言：回溯法

#include<stdio.h>
int n,c,bestp;//物品的个数，背包的容量，最大价值
int p[10000],w[10000],x[10000],bestx[10000];
//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况
void Backtrack(int i,int cp,int cw)
{ //cw当前包内物品重量，cp当前包内物品价值
    int j;
    if(i>n)//回溯结束
    {
        if(cp>bestp)
        {
            bestp=cp;
            for(i=0;i<=n;i++) bestx[i]=x[i];
        }
    }
    else
        for(j=0;j<=1;j++)
        {
            x[i]=j;
            if(cw+x[i]*w[i]<=c)
            {
                cw+=w[i]*x[i];
                cp+=p[i]*x[i];
                Backtrack(i+1,cp,cw);
                cw-=w[i]*x[i];
                cp-=p[i]*x[i];
            }
        }
}
 
int main()
{
    int i;
    bestp=0;
    printf("请输入背包最大容量:\n");
    scanf("%d",&c);
    printf("请输入物品个数:\n");
    scanf("%d",&n);
    printf("请依次输入物品的重量:\n");
    for(i=1;i<=n;i++)
        scanf("%d",&w[i]);
    printf("请依次输入物品的价值:\n");
    for(i=1;i<=n;i++)
        scanf("%d",&p[i]);
    Backtrack(1,0,0);
    printf("最大价值为:\n");
    printf("%d\n",bestp);
    printf("被选中的物品依次是(0表示未选中，1表示选中)\n");
    for(i=1;i<=n;i++)
        printf("%d ",bestx[i]);
    printf("\n");
    return 0;
}

来着：https://blog.csdn.net/ping_lvy/article/details/85078060

C语言：动态规划

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int P[100][100];//前i个物品装入容量为j的背包中获得的最大价值
int max(int a, int b)
{
    if (a >= b)
        return a;
    else return b;
}

int KnapSack(int n, int w[], int v[], int x[], int C)
{
    int i, j;
    for (i = 0; i <= n; i++)
        P[i][0] = 0;
    for (j = 0; j <= C; j++)
        P[0][j] = 0;
    for (i = 0; i < n; i++){
        for (j = 0; j < C+1; j++){
            if (j<w[i])
                P[i][j] = P[i - 1][j];
            else
                P[i][j] = max(P[i - 1][j], P[i - 1][j - w[i]] + v[i]);
        }
    }
    j = C;
    for (i = n - 1; i >= 0; i--)
    {
        if (P[i][j]>P[i - 1][j])
        {
            x[i] = 1;
            j = j - w[i];
        }
        else
            x[i] = 0;
    }
    printf("选中的物品是:\n");
    for (i = 0; i<n; i++)
        printf("%d ", x[i]);
    printf("\n");
    for (int i = 0; i < n; i++){
        for (int j = 0; j < C+1; j++){
            printf("%d\t ", P[i][j]);
            if (j == C){
                printf("\n");
            }
        }
    }
    return P[n - 1][C];

}

int main()
{
    int s;// 获得的最大价值
    int wsum = 0;// ws-物品总重量
    int w[20];// 物品的重量
    int p[20];// 物品的价值
    srand((int)time(0));// 用于生成随机数种子
    // 随机生成数
    printf("物品各重量为:\n");
    for(int i=0; i<20; i++){
        w[i] = rand() % 20 + 1;
        printf("%d ", w[i]);
        wsum += w[i];
    }
    printf("\n%d\n", wsum);
    printf("物品各价值为:\n");
    for(int i=0; i<20; i++){
        p[i] = rand() % 20 + 1;
        printf("%d ", p[i]);
    }
    printf("\n");
    int x[20];// 物品的选取状态
    int n = 20;
    printf("随机生成的背包容量为:\n");
    int M = rand() % wsum + 1;// 随机生成一个小于总重量的数作为背包最大容量
    printf("%d\n", M);
    
    s = KnapSack(n, w, p, x, M);

    printf("最大物品价值为:\n");
    printf("%d\n", s);
    return 0;

}

来着：https://www.cnblogs.com/variance/p/6909560.html

矩形切割问题

问题描述：

? 给定一个100*100的正方形A，假设将A的左上角顶点视为原点，并定义其坐标为(0, 0)。在A中自动生成不超过100个互不相同的点(为简单起见，可假设每个点的横坐标和纵坐标各不相同，这样可保证每条横线或竖线上至多只有一个点，但该约定不是必须的)，且必有一个点恰好在原点上，要求依据这些给定的点切割正方形，切割方向只能向下和向右，每次都寻找最大的长方形进行切割，但所切割的长方形内部不能含有任何其它给定点(给定点可在切割线上)。已经切割的部分不可重复切割，且切割出的部分必须是长方形。对每个给定点都必须做切割操作，并累计切割出的面积，使切割出的总面积尽可能大。

? 将原点作为一个给定点，随机生成其余99个点，并使得这些点的横坐标和纵坐标各不相同。

? 要求至少随机构造10组数据(点)，输出每组数据的运行结果。

? 每组数据的切割总面积与正方形面积的比，给出相应的结论。

C语言：

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

typedef struct coordinate {
    float x;
    float y;
}Point;
float maxs(float a, float b) {
    return a > b ? a : b;
}
void rands(Point xy[], int n) {
    int i;
    srand((unsigned)time(NULL));
    xy[0].x = 0;
    xy[0].y = 0;
    printf("x轴的坐标%lf，y轴的坐标%lf\n", xy[0].x, xy[0].y);
    for (i = 1;i <= n;i++) {
        xy[i].x = rand() / (RAND_MAX + 1.0) * 100;
        xy[i].y = rand() / (RAND_MAX + 1.0) * 100;
        printf("x轴的坐标%lf，y轴的坐标%lf\n", xy[i].x, xy[i].y);
    }
    return;
}
void paixux(Point a[], int low, int high) {
    Point tmp;
    tmp = a[low];
    int i = low;
    int j = high;
    if (low < high) {
        while (i < j) {
            while (i<j && a[j].x>tmp.x) {
                j--;
            }
            a[i] = a[j];
            while (i < j && a[i].x < tmp.x) {
                i++;
            }
            a[j] = a[i];
        }
        a[i] = tmp;
        paixux(a, low, i - 1);
        paixux(a, i + 1, high);
    }
    else {
        return;
    }
}
float max(float a , float b)

{

if( a > b) return a;

return b;

}
float mins(Point xy[], int n) {
    int i;
    float sum = 0;
    float s[4];
    srand((unsigned)time(NULL));
    rands(xy, n);
    paixux(xy, 0, n - 1);
    for (i = 0;i < n;i++)
    {
        if (i == 0)
        {
            s[0] = xy[i].x * xy[i].y;
            s[1] = xy[i].x * (100 - xy[i].y);
            sum += max(s[0], s[1]);
        }
        else if (i == n - 1)
        {
            s[0] = (xy[i].x - xy[i - 1].x) * xy[i].y;
            s[1] = (xy[i].x - xy[i - 1].x) * (100 - xy[i].y);
            s[2] = (100 - xy[i].x) * xy[i].y;
            s[3] = (100 - xy[i].x) * (100 - xy[i].y);
            sum += max(s[0], max(s[1], max(s[2], s[3])));
        }
        else
        {
            s[0] = (xy[i].x - xy[i - 1].x) * xy[i].y;
            s[1] = (xy[i].x - xy[i - 1].x) * (100 - xy[i].y);
            sum += max(s[0], s[1]);
        }
        
    }
    return sum;
}
int main() {
    int s = 10;
    while (s--)
    {
        printf("--------------------开始----------------------------\n");
        int n;
        float m;
        printf("输入随机生成组数：");
        scanf("%d",&n);
        Point xy[100];
        m = mins(xy, n);
        printf("最大矩形面积之和：%f\n", m);
        printf("最大矩形面积之和占总面积的比例：%f\n", m / 10000);
        printf("-------------------结束-----------------------------\n\n");
    }
    
}

C++：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<math.h>
using namespace std;
typedef struct coordinate {
    float x;
    float y;
}Point;
float maxs(float a, float b) {
    return a > b ? a : b;
}
void rands(Point xy[], int n) {
    int i;
    srand((unsigned)time(NULL));
    xy[0].x = 0;
    xy[0].y = 0;
    printf("x轴的坐标%lf，y轴的坐标%lf\n", xy[0].x, xy[0].y);
    for (i = 1;i <= n;i++) {
        xy[i].x = rand() / (RAND_MAX + 1.0) * 100;
        xy[i].y = rand() / (RAND_MAX + 1.0) * 100;
        printf("x轴的坐标%lf，y轴的坐标%lf\n", xy[i].x, xy[i].y);
    }
    return;
}
void paixux(Point a[], int low, int high) {
    Point tmp;
    tmp = a[low];
    int i = low;
    int j = high;
    if (low < high) {
        while (i < j) {
            while (i<j && a[j].x>tmp.x) {
                j--;
            }
            a[i] = a[j];
            while (i < j && a[i].x < tmp.x) {
                i++;
            }
            a[j] = a[i];
        }
        a[i] = tmp;
        paixux(a, low, i - 1);
        paixux(a, i + 1, high);
    }
    else {
        return;
    }
}
float mins(Point xy[], int n) {
    int i;
    float sum = 0;
    float s[4];
    srand((unsigned)time(NULL));
    rands(xy, n);
    paixux(xy, 0, n - 1);
    for (i = 0;i < n;i++)
    {
        if (i == 0)
        {
            s[0] = xy[i].x * xy[i].y;
            s[1] = xy[i].x * (100 - xy[i].y);
            sum += max(s[0], s[1]);
        }
        else if (i == n - 1)
        {
            s[0] = (xy[i].x - xy[i - 1].x) * xy[i].y;
            s[1] = (xy[i].x - xy[i - 1].x) * (100 - xy[i].y);
            s[2] = (100 - xy[i].x) * xy[i].y;
            s[3] = (100 - xy[i].x) * (100 - xy[i].y);
            sum += max(s[0], max(s[1], max(s[2], s[3])));
        }
        else
        {
            s[0] = (xy[i].x - xy[i - 1].x) * xy[i].y;
            s[1] = (xy[i].x - xy[i - 1].x) * (100 - xy[i].y);
            sum += max(s[0], s[1]);
        }
        
    }
    return sum;
}
int main() {
    int s = 10;
    while (s--)
    {
        printf("--------------------开始----------------------------\n");
        int n;
        float m;
        printf("输入随机生成组数：");
        cin>>n;
        Point xy[100];
        m = mins(xy, n);
        printf("最大矩形面积之和：%f\n", m);
        printf("最大矩形面积之和占总面积的比例：%f\n", m / 10000);
        printf("-------------------结束-----------------------------\n\n");
    }
    
}

[数据结构与算法]最大乘积问题+0-1背包问题+矩形分割算法

最大乘积问题+0-1背包问题+矩形分割算法

最大乘积问题

问题描述：

C语言：贪心算法

0-1背包问题

问题描述：

C语言：回溯法

C语言：动态规划

矩形切割问题

问题描述：

C语言：

C++：

目录

文章目录