01背包--hdu

hdu1203

思路：计算一个offer都没有的概率，容斥一下

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iomanip>
#include <stack>

using namespace std;

typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 1e4 + 100;
const int MOD = 1e9 + 9;

#define lson l, m, rt << 14
#define rson m + 1, r, rt << 1 | 1
#define F(i, l, r) for(int i = l;i <= (r);++i)
#define RF(i, l, r) for(int i = l;i >= (r);--i)

int n, m, a[N];
double b[N], dp[N];
int main()
{
    while(cin >> n >> m)
    {
        if(!n && !m) break;
        memset(a, 0, sizeof(a));
        fill(b, b + N, 0);
        fill(dp, dp + N, 1);
        F(i, 1, m) {cin >> a[i] >> b[i];b[i] = 1 - b[i];}
        for(int i = 1;i <= m;++i)
            for(int j = n;j >= a[i];--j)
            dp[j] = min(dp[j], dp[j - a[i]] * b[i]);
        printf("%.1f%%\n", (1 - dp[n]) * 100);
    }
    return 0;
}

01背包--hdu

原文：https://www.cnblogs.com/shuizhidao/p/10915216.html