首页 > ACM题库 > HDU-杭电 > HDU 1684 Projects-动态规划-[解题报告] C++
2013
12-21

HDU 1684 Projects-动态规划-[解题报告] C++

Projects

问题描述 :

In a certain week, a company wants to finish m projects. To this end, the company can employ at most n people from the unemployment agency for a period of one week. Each external employee will cost the company salary euro, unless the project in which he/she is involved is not completed in time. In that case no payment is due.

For each project the company knows from experience the probability that the project will be completed within a week, as a function of the number of employees working on it. These probabilities are given as percentages pij, where i (with 1 ≤ i ≤ m) is the number of the project and j is the number of people working on it. Of course, when nobody is working on a project i, the probability pi0 is zero percent.

If project i is indeed finished within a week, the company earns reward(i) euro; if it is not ready in time, the company has to pay a fine of punishment(i) euro.

Of course the company wants to maximise its total expected profit1 at the end of the week by finding the optimal number of external employees to hire, and how to divide them over the projects. The optimal number of employees is the total number of people needed to achieve the maximal expected profit. Your task in this matter is to calculate this optimal number of external employees. Remember that at most n people are available. Furthermore: if a person is employed, he/she works on one and only one project.

——————————————————————————–

1Let p (0 < p < 1) be the probability that a job is finished in time, and let E1 be the profit in that case. Furthermore, let E2 be the (negative) profit in case the job is not finished in time. Then the expected profit for this particular job is p*E1 + (1 – p)*E2.

输入:

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

One line with one integer m with 1 ≤ m ≤ 100: the number of projects.
One line with one integer n with 0 ≤ n ≤ 100: the maximal number of available employees.
One line with one integer salary with 0 ≤ salary ≤ 1,000: the salary of one employee. Remember that the salary is given in euros.
m lines, each line corresponding to a project i, containing n integers pi1, pi2, …, pin (the percentages, with 0 ≤ pi1, pi2, …, pin ≤ 100), followed by two integers corresponding to the reward and the punishment for project i. All values are separated by single spaces. Both reward and punishment are given in euros and are between 0 and 100,000 (boundaries included).

输出:

For every test case in the input file, the output should contain two lines.

The first line contains the maximal expected profit in eurocents.
The second line contains the total number of external employees that must be hired in order to achieve this maximal expected profit. If the maximal expected profit can be achieved by different (total) numbers of employees, then these different numbers must be given in increasing order. Numbers have to be separated by single spaces.

样例输入:

3
1
4
200
90 100 100 100 2000 0
2
2
100
80 80 2100 500
0 100 1700 500
3
4
100
100 80 80 70 1000 100
100 90 80 90 500 50
100 70 60 50 700 100

样例输出:

162000
1
100000
1 2
190000
3

http://acm.hdu.edu.cn/showproblem.php?pid=1684

题意:有m个工程,最多可以雇佣n个人,已知概率pij表示完成第i个工程雇佣j个人时,能按时完成的概率,同时,已知完成一个工程的奖金和无法完成时的罚款,还有每一个人的工资,当然,如果参与的工程无法按时完成,则参与的人不需要支付工资。求这m个工程的最大利润,同时求出需要的人数,多种方案时,从小到大输出人数。

状态转移方程:
dp[i][j]表示到第i个工程,雇佣j个人的最大利润
dp[i][j]=max(dp[i-1][j-k]+pik *(reward-k*salary)-(100-pik)*punish k表示当前工程雇佣的人数

做题过程:

        根据解题思路写了代码,感觉自己初始化应该对的。但是还是WA了两次,有待找出原因。

        哎,还是初始化的原因:1.不做项目的时候,下一个的期望必须加上上一个的期望。   2.上式中dp[i][j]不是找个最大吗? 它自己应该最先赋值为无穷小。  我还把dp改成__int64了呢。。。。

/*
Pro: 0

Sol:

date:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#define inf 1100000000
#define maxn 101
using namespace std;
int proj_num,peo_num,t,salary;
int p[maxn][maxn],punish[maxn],reward[maxn];
__int64 dp[maxn][maxn];
int main(){
    scanf("%d",&t);
    while(t --){
        memset(dp,0,sizeof(dp));
        scanf("%d%d%d",&proj_num, &peo_num,&salary);
        for(int i = 1; i <= proj_num; i ++){
            for(int j = 1; j <= peo_num; j ++){
                scanf("%d",&p[i][j]);
            }
            scanf("%d%d",&reward[i],&punish[i]);
        }
        //初始化
        dp[0][0] = 0;
        for(int pro = 1; pro <= proj_num; pro ++){
            dp[pro][0] = dp[pro - 1][0]- punish[pro] * 100;//这里下一个要加上上一个!!!
        }
        for(int peo = 1; peo <= peo_num; peo ++){
            dp[1][peo] = p[1][peo] * (reward[1] - salary * peo) - (100 - p[1][peo]) * punish[1];
        }
        //开始dp了
        for(int pro = 2; pro <= proj_num; pro ++){
            for(int tpeo = 0; tpeo <= peo_num; tpeo ++){
                dp[pro][tpeo] = -inf; //这里赋值为无穷小
                for(int npeo = 0; npeo <= tpeo; npeo ++){
                    dp[pro][tpeo] = max(dp[pro][tpeo], dp[pro - 1][tpeo - npeo] + p[pro][npeo] * (reward[pro] - salary * npeo) - punish[pro] * (100 - p[pro][npeo]));
                }
            }
        }
        __int64 Max = -inf;
        int sub = 0,ans[maxn];
        for(int peo = 0; peo <= peo_num; peo ++){
            if(Max < dp[proj_num][peo])
                Max = dp[proj_num][peo];
        }
        for(int peo = 0; peo <= peo_num; peo ++){
            if(dp[proj_num][peo] == Max){
                ans[sub ++] = peo;
            }
        }
        printf("%I64d\n",Max);
        for(int i = 0; i < sub - 1; i ++)
            printf("%d ",ans[i]);   printf("%d\n",ans[sub - 1]);
    }
	return 0;
}

解题报告转自:http://blog.csdn.net/julyana_lin/article/details/7893996


  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮