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;
}
