Java P2240【贪心算法】+【冒泡排序】(求解篇)
查看原帖
Java P2240【贪心算法】+【冒泡排序】(求解篇)
825625
Tenar1ous楼主2022/10/28 11:34

我不知道怎么提交java的代码,所以在这里想让大家帮我看看我写的有没有问题:

import java.util.Scanner;
public class P2240 {
 public static void main(String[] args) {
 Scanner scanner=new Scanner(System.in);
   double TotalWealth=0; //能带走的总价值
   int N=scanner.nextInt();  //N<=100  堆数
   int T=scanner.nextInt();  //T<=1000 承重
   int [] m=new int [101];   
   int [] v=new int [101]; 
   //性价比
   double [] Every_Wealth=new double [101]; 
  for(int i=0;i<N;i++)
  {
   m[i]=scanner.nextInt();
   v[i]=scanner.nextInt();
   Every_Wealth[i]=v[i]/m[i];
  }
   scanner.close();
  //将性价比从大到小排序
  for(int i=0;i<N;i++)
  {
   for(int j=0;j<N;j++)
   {
    if(Every_Wealth[j]<Every_Wealth[j+1])
    {
     double temp=Every_Wealth[j];              Every_Wealth[j]=Every_Wealth[j+1];
     Every_Wealth[j+1]=temp;
     }
    }
   }
  for(int i=0;i<N;i++)
  {
   if(T-m[i]>-0.000001)   
 //先装性价比最高的,如果能全部装下,背包内总价值增加,背包容量减少
   {
    T-=m[i];
    TotalWealth+=v[i];
   }
   else //考虑该堆金币重量大于背包容量的情况
   {
    TotalWealth+=T*Every_Wealth[i]; 
  //将金币分割后带走T重量该性价比的金币
    break;
    }
   }
 System.out.printf("%.2f",TotalWealth);
 }
}
2022/10/28 11:34
加载中...