求解uva 10163 一道DP题ACM高手来 - 数据结构与算法

已结贴√ 问题点数：30 回复次数：15

求解uva 10163 一道DP题ACM高手来

10163守仓库的人
背景：
蓝迪公司有N(1 < = N < = 100)个仓库。公司希望有人来看守它们。现在有M(1 < =M< = 30)人应聘这项工作，公司将雇佣一些人。蓝迪的公司以这些规则雇佣人:
1、每个看守人有一个数值Pi(1<=Pi<=1000)，代表他们的能力值。
2、所有的仓库是一样的。
3、一个仓库只能被一个人看守，但一个人能看守几个仓库。如果一个看守的能力值是Pi，然后他看管K个仓库。他看管的每个仓库的安全值Uj=Pi div K。（Note：Uj、Pi、K是整型），没人照顾的仓库安全值是0。
4、如果所有的仓库给了人去看管，公司将达到一个安全线L=min（Uj）。（PS：这句话我翻译得很纠结，读者可以参照原句：4.If all the storages is at least given to a man, company will get a safe line L=min Uj）
5、每个月蓝迪公司会依据他们的能力值付给每个看守人工资，这意味着如果一个看守人的能力是Pi，则他的工资将是Pi美元/月。公司将支付所有的工资Y美元。
现在蓝迪公司给你一个报表包括所有的信息包括N、M、P，你的任务是给公司一个最佳选择，令公司在安全线L最高的前提下，付给看守人最少的工资。

输入：
输入文件包含多组数据
每组数据由两行组成：
第一行包含两个数字N和M
第二行有M个数字，表示每个守仓库的人的能力值。
相邻的两个数字间有一个空格。
当N=0，M=0时输入结束。
输出：
每个数据应输出最高的L和最小的Y，它们中间应有一个空格分隔。
样例输入：
2 1
7
1 2
10 9
2 5
10 8 6 4 1
5 4
1 1 1 1
0 0
样例输出：
3 7
10 10
8 18
0 0

我的程序错了！！！

程序代码：

#include<cstdio>
#include<cstring>
#define min(a,b)((a)<(b)?(a):(b))

const int INF=2000000000;
const int maxm=30+1;
const int maxn=100+1;

int n,m;
int a[maxm];
int f[maxm][maxn];
int g[maxm][maxn];

void init()
{
     memset(a,0,sizeof(a));
     memset(f,0,sizeof(f));
     for (int i=1;i<=m;i++) scanf("%d",&a[i]);
}


void doit()
{
     for (int i=0;i<=m;i++) f[i][0]=INF;
     for (int i=1;i<=m;i++)
       for (int j=1;j<=n;j++)
         {
             f[i][j]=f[i-1][j];
             for (int k=1;k<=j;k++)
             {
                 int p=min(f[i-1][k-1],a[i]/(j-k+1));
                 if (p>f[i][j]) f[i][j]=p;
             }
         }
}

void ouit()
{
     if (f[m][n]==0) g[m][n]=0;
     else
     { 
         memset(g,127,sizeof(g));
         g[0][0]=0;
         for (int i=1;i<=m;i++)
         {
             int v=a[i];
             int w=a[i]/f[m][n];
             
             for (int j=w;j>=n;j--)
               g[i][j]=min(g[i-1][j],g[i-1][j-w]+v );
         }
     }
     printf("%d %d\n",f[m][n],g[m][n]);
}

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    while (scanf("%d%d",&n,&m),n,m)
    {
          init();
          doit();
          ouit();
    }
    return 0;
}

搜索更多相关主题的帖子: 一个人　

第 2 楼

得分:0

给点提示亦可以啊

第 3 楼

得分:25

程序代码：

#include <iostream>
using namespace std;

const size_t MAX_SIZE = 30;
unsigned short piArray[MAX_SIZE] = {0};
size_t nValue;
size_t mValue;

void outPut();
unsigned int min(unsigned int sum, size_t suffix);
//返回处理的下标值
size_t dealQuestion();
bool getConsoleInputs();
//pi数组降序排序
void sort();

void function()
{
    while (getConsoleInputs())
    {
        sort();
        outPut();
    }
}

int main(void)
{
    function();

    return 0;
}

void outPut()
{
    size_t i=0, suffix=0;
    unsigned int sum = 0;

    suffix = dealQuestion();

    for (; i<=suffix; ++i)
    {
        sum += piArray[i];
    }
   
    printf("%d %d\n\n", min(sum, suffix),sum);
}

unsigned int min(unsigned int sum, size_t suffix)
{
    unsigned int avg = sum/nValue;
    size_t i=0;

    for (; i<=suffix; ++i)
    {
        if (avg > piArray[i])
        {
            avg = piArray[i];
        }
    }

    return avg;
}
//返回处理的下标值
size_t dealQuestion()
{
    unsigned int sum = 0;
    size_t i=0;

    sum += piArray[i];

    while (i<(mValue-1) && sum/nValue < piArray[i+1])
    {
        ++i;
        sum += piArray[i];
    }

    return i;
}

bool getConsoleInputs()
{
    size_t i = 0;

    cin >> nValue >> mValue;
    while (i!=mValue && cin>>piArray[i])
    {
        ++i;
    }

    return (nValue && mValue);
}

//pi数组降序排序
void sort()
{//采用选择法排序
    size_t i, j, k, temp;

    for (i=0; i<mValue-1; ++i)
    {
        k = i;
        for (j=i+1; j<mValue; ++j)
        {
            if (piArray[j] > piArray[k])
            {
                k = j;
            }
        }
        if (k != i)
        {
            temp = piArray[k];
            piArray[k] = piArray[i];
            piArray[i] = temp;
        }
    }
}

图片附件: 游客没有浏览图片的权限，请登录或注册

最后一组不同

第 4 楼

得分:5

楼上的算法是错的。
给几组测试数据吧

input:
4 3
16 8 3
3 3
4 2 3
3 5
15 9 9 8 9
3 3
15 9 8
3 3
15 9 7
output:
5 24
2 6
9 27
8 32
7 22

收到的鲜花

寒风中的细雨于 2011-06-05 02:39 送鲜花 10朵

第 5 楼

得分:0

程序代码：

#include <iostream>
using namespace std;

const size_t MAX_SIZE = 30;
unsigned short piArray[MAX_SIZE] = {0};
unsigned short piSum[MAX_SIZE] = {0};
unsigned short piCost[MAX_SIZE] = {0};
unsigned short piCheck[MAX_SIZE] = {0};

size_t nValue;
size_t mValue;

void outPut();
unsigned short min(size_t suffix, size_t &index);
size_t dealQuestion();//返回处理的下标值
bool getConsoleInputs();
void sort();//pi数组降序排序
unsigned int minSum(size_t suffix);
size_t maxCost(size_t suffix);//返回浪费最大值的下标
void setMaxCost(size_t suffix, unsigned short cost);//设置浪费值
unsigned short meetCounter(size_t suffix, unsigned short cost);
void replace(size_t suffix, unsigned short cost);
bool is_ok(size_t suffix);

void function()
{
    while (getConsoleInputs())
    {
        sort();
        outPut();
    }
}

int main(void)
{
    function();

    return 0;
}

void outPut()
{
    size_t i=0, suffix=0, index;
    unsigned int sum = 0;

    suffix = dealQuestion();

    for (; i<=suffix; ++i)
    {
        sum += piArray[i];
    }
  
    //printf("%d %d\n\n", min(suffix, index), minSum(suffix));
    unsigned short minAvgValue = min(suffix, index);
    printf("%d ",  minAvgValue);

    setMaxCost(suffix, minAvgValue);//设置浪费值
    replace(suffix, minAvgValue);
    printf("%d\n\n", minSum(suffix));
}
//找出所有结果中pi值最低的值 和对应的下标值index
unsigned short min(size_t suffix, size_t &index)
{
    unsigned short temp;
    size_t i=0;

    index = i;
    temp = piArray[i]/piSum[i];
    for (i=1; i<=suffix; ++i)
    {
        if (temp > piArray[i]/piSum[i])
        {
            temp = piArray[i]/piSum[i];
            index = i;
        }
    }

    return temp;
}
//返回处理的下标值
size_t dealQuestion()
{
    unsigned int sum = 0;
    size_t i=0, index;
   
    sum += piArray[i];
    piSum[i] = nValue;
    piCheck[i] = 1;

    while (i<(mValue-1) && min(i, index)<piArray[i+1])
    {//满足最小的平均数也小于piArray[i+1]的值 则加入piArray[i+1]
     //    可以提高平均值 所以piArray[i+1]要加入进来
        --piSum[index];
        ++i;
        ++piSum[i];
        piCheck[i] = 1;
    }

    return i;
}
bool getConsoleInputs()
{
    size_t i = 0;

    cin >> nValue >> mValue;
    while (i!=mValue && cin>>piArray[i])
    {
        piSum[i] = 0;//初始化管理仓库的数量为0
        piCheck[i] = 0;//初始化状态为没有选中状态
        piCost[i] = 0;//初始化浪费的初值
        ++i;
    }

    return (nValue && mValue);
}

//pi数组降序排序
void sort()
{//采用选择法排序
    size_t i, j, k, temp;

    for (i=0; i<mValue-1; ++i)
    {
        k = i;
        for (j=i+1; j<mValue; ++j)
        {
            if (piArray[j] > piArray[k])
            {
                k = j;
            }
        }
        if (k != i)
        {
            temp = piArray[k];
            piArray[k] = piArray[i];
            piArray[i] = temp;
        }
    }
}
//返回最小和
unsigned int minSum(size_t suffix)
{
    unsigned int sum=0;

    for (size_t i=0; i<=mValue-1; ++i)
    {
        if (piCheck[i])
        {
            sum += piArray[i];
        }
        else if (i<=suffix && piSum[i])
        {
            sum += piArray[i];
        }
    }

    return sum;
}

size_t maxCost(size_t suffix)//返回浪费最大值的下标
{
    size_t i = 1, k;

    for (i=0; i<=suffix; ++i)
    {
        if (piCheck[i])
        {
            k = i;
            break;
        }
    }

    for (; i<=suffix; ++i)
    {
        if (piCheck[i] && (piCost[i] > piCost[k]))
        {
            k = i;
        }
    }

    return k;
}

void setMaxCost(size_t suffix, unsigned short cost)//设置浪费值
{
    size_t i = 0;

    for (; i<=suffix; ++i)
    {
        piCost[i] = piArray[i] - cost*piSum[i];
    }
}
//有多少个数据可以进行匹配
unsigned short meetCounter(size_t suffix, unsigned short cost)
{
    unsigned short c = 0;
    size_t i = suffix+1;

    while (i<mValue)
    {
        if (piArray[i] >= cost && !piCheck[i])
        {
            ++c;
        }
        else
        {
            break;
        }
        ++i;
    }

    return c;
}
//进行数据换算
void replace(size_t suffix, unsigned short cost)
{
    size_t i, j;

    i = maxCost(suffix);
    j = meetCounter(suffix, cost);

    while (is_ok(suffix))
    {
        if (j >= piSum[i])
        {//进行处理
            size_t k=1;
            unsigned int sum = 0;

            for (k=0; k<piSum[i]; ++k)
            {
                sum += piArray[suffix+j-k];
            }

            if (sum < piArray[i])
            {
                for (k=0; k<piSum[i]; ++k)
                {
                    piCheck[suffix+j-k] = 1;
                }
                piSum[i] = 0;
            }
        }
       
        piCheck[i] = 0;
        i = maxCost(suffix);
        j = meetCounter(suffix, cost);
    }
}

bool is_ok(size_t suffix)
{
    for(size_t i=0; i<=suffix; ++i)
    {
        if (piCheck[i])
        {
            return true;
        }
    }

    return false;
}

图片附件: 游客没有浏览图片的权限，请登录或注册

第 6 楼

得分:0

图片附件: 游客没有浏览图片的权限，请登录或注册

最后一组不同

第 7 楼

得分:0

能不能解释下思路

第 8 楼

得分:0

可惜，5楼的代码仍然是错的
试试这几组数据：
2 1
1
9 5
5 8 4 8 4
6 5
2 3 1 7 4
5 3
10 3 7
6 6
4 9 7 3 2 6
----------------
0 0
2 20
2 13
3 17
3 18

PS:这题简单的模拟是不行的。我用的是二分法+DP

收到的鲜花

寒风中的细雨于 2011-06-05 23:45 送鲜花 10朵

第 9 楼

得分:0

回复 5楼寒风中的细雨

程序当中
当加入新的看守人员后每个人重新分配仓库所得得数量不正确(没有对应的正确处理过程)

当得出最高L值后进行人员的调整来压缩Y值在处理过程中数量没有正确地匹配

第 10 楼

得分:0

程序代码：

#include <iostream>
using namespace std;

const size_t MAX_SIZE = 30;

struct Pi
{
    unsigned short m_Value;
    unsigned short m_Sum;
   
    bool m_IsChecked;
};

struct Pi piArray[MAX_SIZE];
size_t nValue;//表示仓库的数量
size_t mValue;//表示人的个数

bool getConsoleInputs()
{//获取终端的输入信息
    size_t i=0;

    cin >> nValue >> mValue;
    while (i!=mValue && cin>>piArray[i].m_Value)
    {
        piArray[i].m_Sum = 0;//初始化最初分配到的仓库数量为零
        piArray[i].m_IsChecked = false;
        ++i;
    }

    return (nValue && mValue);
}

/*

 *找出一定范围内[0, suffix]平均Pi值最大的下标值

 */
size_t findMaxAvgPiIndex(size_t suffix)
{
    size_t i=0, k=0;

    for (; i<=suffix; ++i)
    {
        if ((piArray[i].m_Value/piArray[i].m_Sum) >
            (piArray[k].m_Value/piArray[k].m_Sum))
        {
            k = i;
        }
    }

    return k;
}

/*

 *找出一定范围内[0, suffix]平均Pi值最小的下标值

 */
size_t findMinAvgPiIndex(size_t suffix)
{
    size_t i=0, k=0;

    for (; i<=suffix; ++i)
    {
        if ((piArray[i].m_Value/piArray[i].m_Sum) <
            (piArray[k].m_Value/piArray[k].m_Sum))
        {
            k = i;
        }
    }

    return k;
}

/*

 *调整每个人所分配到的仓库数量

 *根据仓库的数量(nValue) 人的个数(mValue)以及Pi

 *进行人员的合理分配使得到最高的安全线

 *返回总的看守仓库的人数

 */
size_t adjustm_Sum()
{
    size_t i, j, suffix=0;
   
    piArray[0].m_Sum = 1;//开始的状态为分配一个仓库数量
    for (i=1; i<nValue; ++i)
    {
        if (i < mValue)
        {
            j = findMaxAvgPiIndex(suffix);
            if (piArray[j].m_Value/(piArray[j].m_Sum+1) >= piArray[suffix+1].m_Value)
            {
                ++(piArray[j].m_Sum);
            }
            else
            {
                ++(piArray[suffix+1].m_Sum);
                ++suffix;//添加新的元素
            }
        }
        else
        {
            j = findMaxAvgPiIndex(suffix);
            ++(piArray[j].m_Sum);
        }
    }

    return suffix+1;
}

//piArray数组降序排序
void sort()
{//采用选择法排序
    size_t i, j, k;
    unsigned short temp;

    for (i=0; i<mValue-1; ++i)
    {
        k = i;
        for (j=i+1; j<mValue; ++j)
        {
            if (piArray[j].m_Value > piArray[k].m_Value)
            {
                k = j;
            }
        }
        if (k != i)
        {
            temp = piArray[k].m_Value;
            piArray[k].m_Value = piArray[i].m_Value;
            piArray[i].m_Value = temp;
        }
    }
}
/*

 *输出最高的安全线

 */
unsigned short showHighL(size_t i)
{
    printf("%d ", piArray[i].m_Value/piArray[i].m_Sum);
    return piArray[i].m_Value/piArray[i].m_Sum;
}
/*****************************************end**********************************/

/*

 *标记需要的记录

 */
void mark(unsigned short minPi)
{
    size_t sum=0;
    size_t i=0;

    for (size_t k=0; k<minPi; ++k)
    {
        for (i=0; i<mValue; ++i)
        {
            if ((piArray[i].m_Value>=minPi) &&
                (!piArray[i].m_IsChecked) &&
                (piArray[i].m_Value%minPi==k) &&
                (sum < nValue))
            {
                sum += piArray[i].m_Value/minPi;
                piArray[i].m_IsChecked = true;
            }
        }
    }
}

/*

 *返回最小和

 */
unsigned short minSum()
{
    unsigned short sum = 0;

    for (size_t i=0; i<mValue; ++i)
    {
        if (piArray[i].m_IsChecked)
        {
            sum += piArray[i].m_Value;
        }
    }

    return sum;
}

/*

 *输出最少的工资

 */
void showLowY(size_t suffix, unsigned short minPi)
{
    mark(minPi);
   
    if (minPi)
    {
        unsigned short result = minSum();
        unsigned short sum = 0;
        for (size_t k=0; k<=suffix; ++k)
        {
            sum += piArray[k].m_Value;
        }
        printf("%d\n\n", result>sum?sum:result);
    }
    else
    {
        printf("0\n\n");
    }
}

void function()
{
    while (getConsoleInputs())
    {
        sort();
        size_t suffix = adjustm_Sum();
        size_t i = findMinAvgPiIndex(suffix-1);
        showLowY(suffix-1, showHighL(i));
    }
}

int main(void)
{
    function();

    return 0;
}