題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2955

題意：小偷想偷銀行的錢給出小偷被抓的概率和n個(gè)銀行，接下來給你n行數(shù)據(jù) 每行給出分別是銀行的錢數(shù)和小偷被抓的概率

求在不大于小偷被抓的概率下能得到銀行的錢數(shù)是多少；

狀態(tài)轉(zhuǎn)移：

把錢數(shù)當(dāng)成體積 ? ? ? ? ? ? ? 不被抓概率當(dāng)成價(jià)值

狀態(tài)方程：dp[j] = max(dp[j],dp[j-v[i]] *w[i];

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; double dp[10005]; int n; double p; double w[105]; int v[105]; void DP(int V) {memset(dp,0,sizeof(dp));dp[0] = 1.0;for(int i = 0;i < n;i++){for(int j = V;j >= v[i];j--){dp[j] = max(dp[j],dp[j-v[i]]*(1-w[i]));}}for(int i = V;;i--){if(dp[i] > 1 - p){printf("%d\n",i);break;}} } int main() {int t;scanf("%d",&t);while(t--){scanf("%lf%d",&p,&n);int sum = 0;for(int i = 0;i < n;i++){scanf("%d%lf",&v[i],&w[i]);sum += v[i];}DP(sum);} }

總結(jié)

以上是生活随笔為你收集整理的hdu-2955（01背包）Robberies的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。