求解一个算法问题

C语言 码拜 9年前 (2015-05-11) 918次浏览 0个评论
 

我要把m(1000左右)条广告交给n(100左右)个人分发,可以利用的信息有之前的后台信息,比如之前完成任务的总数、有效点击数等等。需要一个优化的分配方案。
各位大大求帮忙,提供一个算法思路也好。。。

50分
仅供参考:

//给出12个随机数,分成三组求和,每组的个数不定,要求求出来的三个数之间相差最小,最完美的情况是三个数相等.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <limits.h>
int i,j,k;
int g[12][3]={//可能的分组大小
    { 1, 1,10},
    { 1, 2, 9},
    { 1, 3, 8},
    { 1, 4, 7},
    { 1, 5, 6},
    { 2, 2, 8},
    { 2, 3, 7},
    { 2, 4, 6},
    { 2, 5, 5},
    { 3, 3, 6},
    { 3, 4, 5},
    { 4, 4, 4},
};
int n[12];
int m[12];
int f[12];//当前最小时各数
int g1,g2,g3;//1,2,3组可分配的个数
int n1,n2,n3;//1,2,3组已分配的个数
int f1,f2;//当前最小时1,2组的个数
int s1,s2,s3;//123组的和
int d;//1-2,2-3,3-1组中各数和之间差的绝对值之和
int dmin=INT_MAX;//保存当前d的最小值
void swap(int *pi1,int *pi2) {
    int t;
    t=*pi1;*pi1=*pi2;*pi2=t;
}
void test() {
    s1=0;
    for (i=0;i<g1;i++) s1=s1+n[i];
    s2=0;
    for (i=g1;i<g1+g2;i++) s2=s2+n[i];
    s3=0;
    for (i=g1+g2;i<12;i++) s3=s3+n[i];
    d=abs(s1-s2)+abs(s2-s3)+abs(s3-s1);
    if (d<dmin) {
        dmin=d;
        f1=g1;
        f2=g2;
        for (i=0;i<12;i++) f[i]=n[i];
        printf("(");
        for (i=0;i<g1;i++) printf("%2d,",n[i]);
        printf(")  (");
        for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]);
        printf(")  (");
        for (i=g1+g2;i<12;i++) printf("%2d,",n[i]);
        printf(") %4d\n",dmin);
    } else {
        printf("(");
        for (i=0;i<g1;i++) printf("%2d,",n[i]);
        printf(")  (");
        for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]);
        printf(")  (");
        for (i=g1+g2;i<12;i++) printf("%2d,",n[i]);
        printf(") %4d\n",d);
    }
}
void main() {
    srand(time(NULL));
    for (i=0;i<12;i++) m[i]=rand()%100;
    for (i=0;i<12;i++) printf("%2d,",m[i]);
    printf("\n");
    for (i=1;i<12;i++) {
        for (j=0;j<i;j++) {
            if (m[i]>m[j]) swap(&m[i],&m[j]);//冒泡排序从大到小
        }
    }
    for (i=0;i<12;i++) printf("%2d,",m[i]);
    printf("\n");
    for (k=0;k<12;k++) {//在12种分组方法中
        //取第i种分组方法
        g1=g[k][0];
        g2=g[k][1];
        g3=g[k][2];
        printf("%2d-%2d,%2d,%2d\n",k,g1,g2,g3);
        //将从大到小12个数双向轮流分配到三个组中
        n1=0;
        n2=0;
        n3=0;
        for (j=0;j<12;j++) {
            switch (j%6) {
            case 0:
        redo:
                if (n1<g1) {
                    n[n1]=m[j];
                    n1++;
                    break;
                }
            case 1:
                if (n2<g2) {
                    n[g1+n2]=m[j];
                    n2++;
                    break;
                }
            case 2:
                if (n3<g3) {
                    n[g1+g2+n3]=m[j];
                    n3++;
                    break;
                }
            case 3:
                if (n3<g3) {
                    n[g1+g2+n3]=m[j];
                    n3++;
                    break;
                }
            case 4:
                if (n2<g2) {
                    n[g1+n2]=m[j];
                    n2++;
                    break;
                }
            case 5:
                if (n1<g1) {
                    n[n1]=m[j];
                    n1++;
                    break;
                }
            default:goto redo;
            }
        }
        test();
    }
    printf("---------------------------------------------------\n");
    g1=f1;
    g2=f2;
    for (i=0;i<12;i++) n[i]=f[i];
    printf("(");
    for (i=0;i<g1;i++) printf("%2d,",n[i]);
    printf(")  (");
    for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]);
    printf(")  (");
    for (i=g1+g2;i<12;i++) printf("%2d,",n[i]);
    printf(") %4d\n",dmin);
}
引用 1 楼 zhao4zhong1 的回复:

仅供参考:

//给出12个随机数,分成三组求和,每组的个数不定,要求求出来的三个数之间相差最小,最完美的情况是三个数相等.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <limits.h>
int i,j,k;
int g[12][3]={//可能的分组大小
    { 1, 1,10},
    { 1, 2, 9},
    { 1, 3, 8},
    { 1, 4, 7},
    { 1, 5, 6},
    { 2, 2, 8},
    { 2, 3, 7},
    { 2, 4, 6},
    { 2, 5, 5},
    { 3, 3, 6},
    { 3, 4, 5},
    { 4, 4, 4},
};
int n[12];
int m[12];
int f[12];//当前最小时各数
int g1,g2,g3;//1,2,3组可分配的个数
int n1,n2,n3;//1,2,3组已分配的个数
int f1,f2;//当前最小时1,2组的个数
int s1,s2,s3;//123组的和
int d;//1-2,2-3,3-1组中各数和之间差的绝对值之和
int dmin=INT_MAX;//保存当前d的最小值
void swap(int *pi1,int *pi2) {
    int t;
    t=*pi1;*pi1=*pi2;*pi2=t;
}
void test() {
    s1=0;
    for (i=0;i<g1;i++) s1=s1+n[i];
    s2=0;
    for (i=g1;i<g1+g2;i++) s2=s2+n[i];
    s3=0;
    for (i=g1+g2;i<12;i++) s3=s3+n[i];
    d=abs(s1-s2)+abs(s2-s3)+abs(s3-s1);
    if (d<dmin) {
        dmin=d;
        f1=g1;
        f2=g2;
        for (i=0;i<12;i++) f[i]=n[i];
        printf("(");
        for (i=0;i<g1;i++) printf("%2d,",n[i]);
        printf(")  (");
        for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]);
        printf(")  (");
        for (i=g1+g2;i<12;i++) printf("%2d,",n[i]);
        printf(") %4d\n",dmin);
    } else {
        printf("(");
        for (i=0;i<g1;i++) printf("%2d,",n[i]);
        printf(")  (");
        for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]);
        printf(")  (");
        for (i=g1+g2;i<12;i++) printf("%2d,",n[i]);
        printf(") %4d\n",d);
    }
}
void main() {
    srand(time(NULL));
    for (i=0;i<12;i++) m[i]=rand()%100;
    for (i=0;i<12;i++) printf("%2d,",m[i]);
    printf("\n");
    for (i=1;i<12;i++) {
        for (j=0;j<i;j++) {
            if (m[i]>m[j]) swap(&m[i],&m[j]);//冒泡排序从大到小
        }
    }
    for (i=0;i<12;i++) printf("%2d,",m[i]);
    printf("\n");
    for (k=0;k<12;k++) {//在12种分组方法中
        //取第i种分组方法
        g1=g[k][0];
        g2=g[k][1];
        g3=g[k][2];
        printf("%2d-%2d,%2d,%2d\n",k,g1,g2,g3);
        //将从大到小12个数双向轮流分配到三个组中
        n1=0;
        n2=0;
        n3=0;
        for (j=0;j<12;j++) {
            switch (j%6) {
            case 0:
        redo:
                if (n1<g1) {
                    n[n1]=m[j];
                    n1++;
                    break;
                }
            case 1:
                if (n2<g2) {
                    n[g1+n2]=m[j];
                    n2++;
                    break;
                }
            case 2:
                if (n3<g3) {
                    n[g1+g2+n3]=m[j];
                    n3++;
                    break;
                }
            case 3:
                if (n3<g3) {
                    n[g1+g2+n3]=m[j];
                    n3++;
                    break;
                }
            case 4:
                if (n2<g2) {
                    n[g1+n2]=m[j];
                    n2++;
                    break;
                }
            case 5:
                if (n1<g1) {
                    n[n1]=m[j];
                    n1++;
                    break;
                }
            default:goto redo;
            }
        }
        test();
    }
    printf("---------------------------------------------------\n");
    g1=f1;
    g2=f2;
    for (i=0;i<12;i++) n[i]=f[i];
    printf("(");
    for (i=0;i<g1;i++) printf("%2d,",n[i]);
    printf(")  (");
    for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]);
    printf(")  (");
    for (i=g1+g2;i<12;i++) printf("%2d,",n[i]);
    printf(") %4d\n",dmin);
}

我忘记说明了。。。这个用户是有优劣等级的。。。就是这里想不明白了,怎么约束各个个体之间的能力差异然后得到最佳分配。

50分
好似“任务分配问题”,看看能不能抽象成这个问题,用匈牙利算法解决

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明求解一个算法问题
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!