杭电1203java实现

I need a offer题目链接
学习了其他人的才会的用Java复述一遍
首先，对于概率问题，如果直接从正面考虑会比较麻烦，不知直接从反面考虑不被offer 的概率。这是一道dp题，dp过了没啥问题，问题是贪心的代码也过了。。。。。。。尴尬并且测试数据有的dp和贪心结果不同，discuss里有。
dp ：01背包问题，核心就是每当多一所学校时，看钱够不够，如果够，就比较采纳和不采纳这所学校的概率，如果不够，就不采纳。状态转移方程：
dp[钱数][学校数]=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]));等于号要有，有的大学可能不要钱
else dp[i][j]=dp[i][j-1];
还有注意的是初始化问题，初始应该为1而不是0，因为刚开始肯定不被offer，所以不被offfer概率为1，注意的就是初始dp[0][学校数]的时候看看这所学校是不是免费的，如果是免费的，那么概率就是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();//钱数 int m=sc.nextInt();//数据个数 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])); } else dp[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 自动生成的方法存根
		return d>e?e:d;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

附上贪心法的代码：（贪心能过但是其实不对）

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();//钱数
		int m=sc.nextInt();//数据个数
		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) "%");
	 }
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/79631723