购物单

使用纯搜索的方法，求解空间是n个物品中选择购买m个物品(m<n)的排列组合，但是因为这样求解空间过大，一一列举时间不够，所以我采用了蒙特卡洛算法，每次循环列举n个例子，直到达到停止条件，不过很难在1s内收敛到最优解。
#include 
#include 
#include  // 包含时间库用于种子初始化
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);
    }
    //初始化随机数种子
    srand(time(NULL));
    //创建求解空间，求解空间为n*n，为1则买这个物品，为0则不
    char ** solveplace=(char **) malloc(num*sizeof(char*));// 动态分配一个 n x n 的二维数组
    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<70000)
    {
        goto SOLVE;
    }
    else
        printf("%d",satisfaction_max);
    return 0;
}

#include <stdio.h>
#include <malloc.h>
#include <math.h>
struct goodssub{
    int price;
    int worth;
    struct goodssub * nxt;
};
struct goodsmain{
    int index;
    int price;
    int worth;
    int sub_num;
    int a[32000];
    struct goodssub* mysub;
};
struct goodsmain goods[60];
int howmanyzero(int n){
    int ret = 0;
    while (n % 10 == 0){
        ret ++;
        n/=10;
    }
    return ret;
}
int main() {
    int price, totnum, mainnum=0;
    scanf("%d %d", &price, &totnum);
    int tmp[60][3];
    int tmpnum=0;
    int minzero = 100;
    for (int i=0; i < totnum; i++){
        int v, p, q;
        scanf("%d %d %d", &v, &p, &q);
        if (minzero > howmanyzero(v)) minzero = howmanyzero(v);
        if (q == 0){
            goods[mainnum].index = i + 1;
            goods[mainnum].price = v;
            goods[mainnum].worth = p;
            goods[mainnum].sub_num = 0;
            goods[mainnum].mysub = NULL;
            mainnum ++;
        }else {
            tmp[tmpnum][0] = v;
            tmp[tmpnum][1] = p;
            tmp[tmpnum][2] = q;
            tmpnum ++ ;
        }
    }
    int  myzero = pow(10, minzero);
    for (int i=0; i < mainnum; i++) goods[i].price /= myzero;
    price /= myzero;
    for (int i=0; i < tmpnum; i++) tmp[i][0] /= myzero;
    for (int i=0; i < tmpnum; i++){
        int thisindex = 0;
        int j;
        for(j=0; j < mainnum; j++) if (goods[j].index == tmp[i][2]) break;
        struct goodsmain *gp = &goods[j];
        struct goodssub *gs ;
        if (gp->sub_num == 0){
            gp->mysub = malloc(sizeof(struct goodssub));
            gs =  gp->mysub;
        }else {
            gs =  gp->mysub;
            for (int ii=0; ii < gp->sub_num - 1; ii++) gs = gs->nxt;
            gs -> nxt = malloc(sizeof(struct goodssub));
            gs = gs->nxt;
        }
        gs->price = tmp[i][0];
        gs->worth = tmp[i][1];
        gs->nxt = NULL;
        gp->sub_num ++;
    }
    int * aaa = malloc(sizeof(int) * (price + 1) * (mainnum + 1));
    for (int i=0; i <= price; i++) aaa[i] = 0;
    for (int i=0; i < mainnum; i++){
        if (goods[i].sub_num == 0){
            for (int ii=0; ii <= price; ii++) goods[i].a[ii] = (ii >= goods[i].price)?goods[i].price * goods[i].worth:0;
        }else{
            int *aa = malloc(sizeof(int) * (price + 1) * (goods[i].sub_num + 1));
            for (int ii=goods[i].price; ii <= price; ii++) aa[ii] = goods[i].price * goods[i].worth;
            struct goodssub *gs = goods[i].mysub;
            for (int jj = 1; jj <= goods[i].sub_num; jj++){
                for (int ii=goods[i].price; ii <= price; ii++){
                    int max = aa[(jj-1) * (price + 1) + ii];
                    if (ii - gs->price >= goods[i].price)
                        if (aa[(jj-1) * (price + 1) + ii - gs->price] + gs->price * gs->worth > max) 
                            max = aa[(jj-1) * (price + 1) + ii - gs->price] + gs->price * gs->worth;
                    aa[jj * (price + 1) + ii ] = max;
                }
                gs = gs->nxt;
            }
            for (int ii=0; ii <= price; ii++) goods[i].a[ii] = (ii < goods[i].price)?0:aa[goods[i].sub_num * (price + 1) + ii];
            free(aa);
        }
        for (int j=0; j<=price; j++){
            int max = 0;
            for (int k=0; k <= j; k++)
                if (aaa[(i) * (price + 1) + k] + goods[i].a[j-k] > max) max = aaa[(i) * (price + 1) + k] + goods[i].a[j-k];
            aaa[(i+1)*(price+1)+j] = max;
        }

    }
    printf("%d", aaa[mainnum * (price + 1) + price] * myzero);
    return 0;
}

#include <stdio.h>

typedef struct goods{
    int prices; //物品的价格
    int value; //满意度
}GOODS ;

int max(int a, int b)
{
    return a>b ? a:b;
}

int main() {
    int N,m,a,b,c;
    GOODS goods[60][3] = {0}; //goods[i][0]代表主件、goods[i][1]代表附件1、goods[i][2]代表附件2
    scanf("%d %d", &N, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        a /= 10; b *= a;
        if (c == 0) 
        {
            goods[i][0].prices = a; goods[i][0].value = b;
        } 
        else 
        {
            if (goods[c][1].prices == 0) 
            {
                goods[c][1].prices = a; goods[c][1].value = b;
            } 
            else 
            {
                goods[c][2].prices = a; goods[c][2].value = b;
            }
        }
    }

    N /= 10; //每件物品的价格（都是 10 元的整数倍）
    int dp[60][3200] = {0};
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=N; j++)
        {
            int a = goods[i][0].prices, b = goods[i][0].value;
            int c = goods[i][1].prices, d = goods[i][1].value;
            int e = goods[i][2].prices, f = goods[i][2].value;
            dp[i][j] = j >= a ? max(dp[i-1][j-a] + b, dp[i-1][j]) : dp[i-1][j];
            dp[i][j] = j >= (a+c) ? max(dp[i-1][j-a-c] + b + d, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a+e) ? max(dp[i-1][j-a-e] + b + f, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a+c+e) ? max(dp[i-1][j-a-c-e] + b + d + f, dp[i][j]) : dp[i][j];     
        }
    }

    printf("%d", dp[m][N]*10);
    return 0;
}

//四种情况：1、主件；2、主件+附件1；3、主件+附件2；4、主件+附件1+附件2
//dp[i][j] = max(物品不放入背包，主件，主件+附件1，主件+附件2，主件+附件1+附件2)
/*
int a = prices[i][0], b = value[i][0];
int c = prices[i][1], d = value[i][1];
int e = prices[i][2], f = value[i][2];
dp[i][j] = j >= a ? max(dp[i-1][j-a] + b, dp[i-1][j]) : dp[i-1][j];
dp[i][j] = j >= (a+c) ? max(dp[i-1][j-a-c] + b + d, dp[i][j]) : dp[i][j];
dp[i][j] = j >= (a+e) ? max(dp[i-1][j-a-e] + b + f, dp[i][j]) : dp[i][j];
dp[i][j] = j >= (a+c+e) ? max(dp[i-1][j-a-c-e] + b + d + f, dp[i][j]) : dp[i][j];
*/

#include <stdio.h>
#define       N        60
#define       M        32000
int price[N][3],value[N][3],f[N][M];    //二维数组的第一列代表主件的属性，第2和3列分别表示附件1和2的属性
int max(int a,int b)                    //其中price二维数组存储价格，value二维数组存储价值（价格*重要度）
{                                       //f二维数组的值，表示在n个主件（包含附件）可购买，且预算为m情况下的最大价值之和
    return (a>b?a:b);
}
int main()
{
    int m,n,i,p1,w,z,j,p[N][3],v[N][3],temp[5];    //二维数组p和v与上述描述的二维数组作用相似，不过此时是从第1行依行逐次存放物品属性
    scanf("%d%d",&m,&n);                  //输入钱m和可购买的物件n
    for(i=1;i<=n;i++)                    
    {
        scanf("%d%d%d",&p1,&w,&z);      //输入每一件物品的价格p，重要度w，是否主件标志z
        if(z==0)                
        {
            price[i][0]=p1;            //若z==0，表示为主件，属性存放在第i行的第0列
            value[i][0]=p1*w;
        }
        else
        {
            if(price[z][1]==0)        //若有第一个出现的附件，其属性存放在第z行的第1列
            {
                price[z][1]=p1;
                value[z][1]=p1*w;
            }
            else
            {
                price[z][2]=p1;        //若有第二个出现的附件，其属性存放在第z行的第2列
                value[z][2]=p1*w;                 
            }
        }
    }
    for(i=1,j=1;i<=n;i++)            //将以上二维数组的值，按顺序转移到新的二维数组中，这样就不会有很多附件的0的数据穿插其中
    {
        if(price[i][0]!=0)
        {
            p[j][0]=price[i][0];p[j][1]=price[i][1];p[j][2]=price[i][2];
            v[j][0]=value[i][0];v[j][1]=value[i][1];v[j][2]=value[i][2];
            j++;
        }
    }
    n=j-1;                      //n表示主件个数
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            for(w=0;w<5;w++)
            {
                temp[w]=0;        //temp数组存放价值
            }
            temp[0]=f[i-1][j];    //temp[0]表示不买第i个主件所能够得到的最大价值之和
            if(j>=p[i][0])
            {
                temp[1]=f[i-1][j-p[i][0]]+v[i][0];    //temp[1]表示买第i个主件（仅主件）后所能够得到的最大价值之和
            }
            if(j>=(p[i][0]+p[i][1]))
            {
                temp[2]=f[i-1][j-p[i][0]-p[i][1]]+v[i][0]+v[i][1];        //temp[2]表示买第i个主件+附件1后所能够得到的最大价值之和
            }
            if(j>=(p[i][0]+p[i][2]))
            {                                                            //下同
                temp[3]=f[i-1][j-p[i][0]-p[i][2]]+v[i][0]+v[i][2];
            }
            if(j>=(p[i][0]+p[i][1]+p[i][2]))
            {
                temp[4]=f[i-1][j-p[i][0]-p[i][1]-p[i][2]]+v[i][0]+v[i][1]+v[i][2];
            }
            f[i][j]=max(temp[4],max(max(temp[0],temp[1]),max(temp[2],temp[3])));        //取数组temp内最大值，存放于f[i][j]
        }
    }
    printf("%d\n",f[n][m]);            //打印f[n][m],即在n个主件（包含附件）可购买，且预算为m情况下的最大价值之和
    return 0;
}

//写了很久，终于写出来了，dp是真难啊

#include <stdio.h>
int max(int a,int b){
    return a>b?a:b;
}
int main(void){
    //背包问题延展，有附件，最多两个，要考虑到附件
    int N,m;
    while (scanf("%d %d",&N,&m)!=EOF) {
        int value[63][3]={0};
        int weight[63][3]={0};
        int q=0,p=0,v=0;
        for(int i=1;i <= m;i++)
        {
            scanf("%d %d %d",&v,&p,&q);
              if(q){//附件
                if(!value[q][1]){//第一个附件
                    value[q][1] = v;//价格
                    weight[q][1] = v*p;//重要度
                }else{//第二个附件
                    value[q][2] = v;
                    weight[q][2] = ***bsp;               }
            }else{//主件
                value[i][0] = v;
                weight[i][0] = ***bsp;           }
        }
        int n=N/10,value_total = 0,weight_total = 0;
        int total_max[3200] = {0};
        for(int i=1;i <= m;i++)
        {
            for(int j=n;j >= value[i][0]/10;j--)
            {
                total_max[j] = max(total_max[j],total_max[j - value[i][0]/10] + weight[i][0]);
            
            value_total = value[i][1]/10 + value[i][0]/10;
            weight_total = weight[i][1] + weight[i][0];
            if(value[i][1] && j >= value_total)
            {
                total_max[j] = max(total_max[j],total_max[j - value_total] + weight_total);
            }
                value_total += value[i][2]/10;
            weight_total += weight[i][2];
            if(value[i][2] && j >= value_total)
            {
                total_max[j] = max(total_max[j],total_max[j - value_total] + weight_total);
            }
        }
        }
        printf("%d\n",total_max[n]);
    }
    return 0;
    }