HDU 2955 Robberies

Robberies

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3083    Accepted Submission(s): 1160

Problem Description

The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.


For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.


His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.

 

Input

The first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj . 
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .

 

Output

For each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.

Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.

 

Sample Input

3 0.04 3 1 0.02 2 0.03 3 0.05 0.06 3 2 0.03 2 0.03 3 0.05 0.10 3 1 0.03 2 0.02 3 0.05

 

Sample Output

2 4 6

题意：在不被抓的前提下（不被抓的概率大），偷尽可能多的钱。

 

 

开始看的时候，还没看清楚就以为是01背包，把概率成了容量，写了这个错代码。因为概率要乘的。

 

 

 

#include <stdio.h>
#include <string.h>

int main()
{
    int t, n, m, f[110], i, c, w, v;
    double p, cf;


    scanf("%d", &t);
    while (t--)
    {
        scanf("%lf%d", &p, &n);
        m = (int)100 * p;

        memset(f, 0, sizeof(f));

        for (i = 1; i <= n; i++)
        {
            scanf("%d%lf", &w, &cf);
            c = (int)100 * cf;
            for (v = m; v >= c; v--)
            {
                if (f[v] < f[v - c] + w)
                {
                    f[v] = f[v - c] + w;
                }
            }
        }

        printf("%d\n", f[m]);
        
    }
    return 0;
}

 

 

后来看了下人家的报告。是用 f[i]表示偷到偷的钱的总数为i，不被抓的概率最大。（为什么最后不是直接f[cost]，代码为什么要通过for来找i,想通了再补充）。

 

自己又想了下能不能f[i]代表概率为i,偷到的钱最多。。。是不行的。。。因为，f[]中括号里，当选择的时候，2个小于1的数相乘会更小，如0.01*0.02就成了0.0002 ，而我们之前只将其乘以100来使之变成整数。现在要乘以10000了，而且我们选择的时候有f[i-c] +w  (一般公式，可以乘除，就如现在这题。)中的f[]是利用前面记录的数，如果是用这个状态的话，就用利用不了前面记录的数，所以f[]里一般要用减号（到目前为止只见过）。

 

从这题体会到DP一般都是这样：目的是为了求结果的状态，但是，由于求的过程中要利用中间的一些状态的值，所以，尽管我们最后求的不是他，但是也要记录。

然后，初始化也很重要，例如这题，中的代码也有说到。。。我们初始化是为了后面的max(a,b)中的选择，和有一个边界值，就是说符合两个原则：一，必选一个原则。二，符合实际原则。

 

DP：

1~输入过程。

2~初始化过程。

3~记录过程。

4~寻找适合答案过程（有时候没，有的话要看题目怎么问，一般都加个for（i.....）可能是找适合的 i ，也可能找适合的f[i]）。

 

#include <stdio.h>
#include <string.h>

int main()
{
    int t, n, i, c[110], v, cost;
    double p, p1[110],f[10010];


    scanf("%d", &t);
    while (t--)
    {
        scanf("%lf%d", &p, &n);
        
        memset(f, 0, sizeof(f));//刚才说到初始化的问题。如这里，其实可以不一定是0，但是这里的初始化是为了
//其中一个是已经赋值，而另一个未赋过值，时一定选择赋过值的那个，(类比用max标记最大值是max=-INF为初值)。所以，这里如果有赋过
//值的话都大于0，所以其实f[1.....n]赋初值为 <= 0的数都可以。【必选第一个值原则】


        f[0] = 1;//而这个初值一定要为1,因为当没偷过1分钱的时候，是不可能被抓的既【符合实际原则】


        cost = 0;
        for (i = 1; i <= n; i++)
        {
            scanf("%d%lf", &c[i], &p1[i]);
            cost += c[i];
            
        }



        for (i = 1; i <= n; i++)//记录过程。
        {
            for (v = cost; v >= c[i]; v--)
            {
                if (f[v] < f[v - c[i]] * (1 - p1[i]))
                {
                    f[v] = f[v - c[i]] * (1 - p1[i]);
                }
            }
        }



        for (i = cost; i >= 0; i--)//找适合答案过程。
        {
            if (f[i] >= (1 - p))
            {
                break;
            }
        }
        printf("%d\n", i);
        
    }
    return 0;
}

 

 

2012/9/3

同一题，不同时间做的效果完全不一样。。。。

 

题目要求在一个限制的概率下，的最大钱。。。。

因为概率那些事小数，于是我确定了，钱是费用，概率是价值。。。。。我们希望相同的概率下被抓的概率尽量低，所以我们用背包。。。要么求被抓的最小概率。

要么就求不被抓的最大概率。。。但是看到这个公式f[v] = max(f[v], f[v-c] * w);后面那里表示已经选择了抢该银行，也就表示已经没抓到，所以我们要选后面那个（求不被抓的最大概率）

 

 

特别注意的一点是，这是恰好装满的类型。。。。所以初始化特别注意。。。。

 

#include <iostream>
#include <algorithm>
using namespace std;


const int M = 10010;//V
const int N = 110;//n

int c[N],/* w[N],*/ n1[N];//c:费用 w:价值 n1:数量
double w[N];
double f[M];//f[与V有关],c和w[与n]有关
int v, V, V1;//V:容量 V1:容量2
int n;

//01背包
void ZeroOnePack(int c, double w)
{
for (int v = V; v >= c; v--)
{
f[v] = max(f[v], f[v-c] * w);
}
}

//完全背包
void CompletePack(int c, int w)
{
for (int v = c; v <= V; v++)
{
f[v] = max(f[v], f[v-c] + w);
}
}

//多重背包，二进制。
void MultiplePack(int c, int w, int n1)
{
if (c * n1 >= V)
{
CompletePack(c, w); 
}
else
{
int k = 1;
while (k < n1)
{
ZeroOnePack(k*c, k*w);
n1 -= k;
k <<= 1;
}
ZeroOnePack(n1*c, n1*w);
}
}



int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        
        double lowest;
        scanf("%lf%d", &lowest, &n);
        V = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d%lf", c + i, w + i);
            w[i] = 1 - w[i];//转成不被抓的概率
            V += c[i];
        }

    
        memset(f, 0, sizeof(f));//没有符合条件（恰好装满）的,为了保证后面改变该值，所以初始化为最小值（即最不优解）
        f[0] = 1;//符合条件的最优

        for (int i = 0; i < n; i++)
        {
            ZeroOnePack(c[i], w[i]);

        }

        int i;
        for (i = V; i > 0; i--)//从后往前扫找答案
        {
            if (1 - f[i] < lowest)
            {
                break;
            }
        }

        printf("%d\n", i);
    }
    return 0;
}