HJ16 购物单 题解，用蒙特卡洛算法搜索

#include <stdio.h>

#include <stdlib.h>

#include <time.h> // 包含时间库用于种子初始化

struct object

{

    int price;

    int importance;

    int kind;

};

int main() {

    int money, num;

    int satisfaction_max;

    scanf("%d %d",&money, &num);

    struct object *items= (struct object *)malloc(num*3*sizeof(int));

    //储存数据

    for(int i=0;i<num;i++)

    {

        scanf("%d %d %d",&items[i].price,&items[i].importance,&items[i].kind);

    }

    //创建求解空间，求解空间为n*n，为1则买这个物品，为0则不

    char ** solveplace=(char **) malloc(num*sizeof(char*));// 动态分配一个 n x n 的二维数组

    //初始化随机数种子

    srand(time(NULL));

    int satisfaction_max_stableCount = 0;//蒙特卡洛算法停止条件

    int satisfaction_max_before=0;

    for(int i=0;i<num;i++)

    {

        solveplace[i]=(char*)malloc(num*sizeof(char));

    }  

    SOLVE:

    //使用随机数创建求解例子

    for(int i=0;i<num;i++)

    {

        for(int j=0;j<num;j++)

        {

            double rand_num = (double)rand() / RAND_MAX; // 生成一个 0 到 1 之间的随机数            

            if(rand_num<0.5)

                solveplace[i][j]=0;

            else

                solveplace[i][j]=1;

        }

    }

    //将不符合附件规定的删除

    for(int i=0;i<num;i++)

    {

        for(int j=0;j<num;j++)

        {

            if(solveplace[i][j]&&items[j].kind)//如果它是附件

            {

                if(solveplace[i][items[j].kind-1]==0)//如果这个附件的主件没有选择

                    solveplace[i][0]=-1;//剔除这个求解，用-1作为标志

            }

        }

    }

    //计算所用的钱，将大于所用钱的的删除

    for(int i=0;i<num;i++)

    {

        if(solveplace[i][0]==-1)

            continue;

        int money_=0;

        for(int j=0;j<num;j++)

        {

            if(solveplace[i][j])

                money_+=items[j].price;

        }

        if(money_>money)//价格超了，删除这个求解

            solveplace[i][0]=-1;

    }

    //寻找剩余可行解中重要值最大的

    for(int i=0;i<num;i++)

    {

        if(solveplace[i][0]==-1)

            continue;

        int satisfaction=0;

        for(int j=0;j<num;j++)

        {

            if(solveplace[i][j])

                satisfaction+=items[j].price*items[j].importance;

        }

        if(satisfaction>satisfaction_max)

            satisfaction_max = satisfaction;

    }

    if(satisfaction_max==satisfaction_max_before)

        satisfaction_max_stableCount++;

    satisfaction_max_before = satisfaction_max;

    //蒙特卡洛算法停止判断

    if(satisfaction_max_stableCount<100000)

    {

        goto SOLVE;

    }

    else

        printf("%d",satisfaction_max);

    return 0;

}