I need a offer題目鏈接
學(xué)習(xí)了其他人的才會(huì)的用Java復(fù)述一遍
首先，對于概率問題，如果直接從正面考慮會(huì)比較麻煩，不知直接從反面考慮不被offer 的概率。這是一道dp題，dp過了沒啥問題，問題是貪心的代碼也過了。。。。。。。尷尬并且測試數(shù)據(jù)有的dp和貪心結(jié)果不同，discuss里有。
dp ：01背包問題，核心就是每當(dāng)多一所學(xué)校時(shí)，看錢夠不夠，如果夠，就比較采納和不采納這所學(xué)校的概率，如果不夠，就不采納。狀態(tài)轉(zhuǎn)移方程：
dp[錢數(shù)][學(xué)校數(shù)]=dp[i][j];
if(i-a[j]>=0） dp[i][j]=min(dp[i][j-1],dp[i-a[j]][j-1]*(1-b[j]));等于號要有，有的大學(xué)可能不要錢
else dp[i][j]=dp[i][j-1];
還有注意的是初始化問題，初始應(yīng)該為1而不是0，因?yàn)閯傞_始肯定不被offer，所以不被offfer概率為1，注意的就是初始dp[0][學(xué)校數(shù)]的時(shí)候看看這所學(xué)校是不是免費(fèi)的，如果是免費(fèi)的，那么概率就是1-b[j];(如果還有，就是（1-b[j]）*b[j2])等等。
附上代碼如下：

import java.util.Scanner; /** dp算法*/ public class 杭電1203 {public static void main(String[] args){ Scanner sc=new Scanner(System.in);while(sc.hasNext()){int n=sc.nextInt();//錢數(shù)int m=sc.nextInt();//數(shù)據(jù)個(gè)數(shù)if(m==0&&n==0) {break;}float dp[][]=new float[n 1][m 1];int a[]=new int[m 1];//錢float b[]=new float[m 1];//概率for(int i=1;i=0){dp[i][j]=min(dp[i][j-1],dp[i-a[j]][j-1]*(1-b[j])); }elsedp[i][j]=dp[i][j-1]; } }float value=(100-dp[n][m]*100);System.out.println(String.format("%.1f", value) "%"); }}private static float min(float d, float e) {// TODO 自動(dòng)生成的方法存根return d>e?e:d;} }

附上貪心法的代碼：（貪心能過但是其實(shí)不對）

import java.util.Scanner; /** 貪心算法*/ public class 杭電1203 {public static void main(String[] args){ Scanner sc=new Scanner(System.in);while(sc.hasNext()){int n=sc.nextInt();//錢數(shù)int m=sc.nextInt();//數(shù)據(jù)個(gè)數(shù)if(m==0&&n==0) {break;}int a[]=new int[m 1];float b[]=new float[m 1];float c[]=new float[m 1];int money=n;float sum=1;for(int i=1;i=a[i]) {sum=sum*(1-b[i]);money-=a[i];}}float value=(100-sum*100);System.out.println(String.format("%.1f", value) "%");}} } 《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的杭电1203java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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