#include<stdio.h> int main() { int n,t; int w[100],v[100]; double ans,p[100]; while(scanf("%d %d",&n,&t)!=EOF) { for(int i = 0;i<n;i++) { scanf("%d %d",&w[i],&v[i]); p[i] = v[i]*1.0/w[i]; } ans = 0; int t2; double t1; for(int i = 0;i<n-1;i++) for(int j = 0;j<n-i-1;j++) if(p[j]<p[j+1]) { t1 = p[j]; p[j] = p[j+1]; p[j+1] = t1; t2 = w[i]; w[i] = w[i+1]; w[i+1] = t2; } if(t<=0) printf("0.00\n"); else { int q = 0; for(int i = 0;i<n;i++) { for(int j = 1;j<=w[i];j++) { ans = ans+p[i]; t--; if(t==0) { q = 1; break; } } if(q) break; } printf("%.2lf\n",ans); } } return 0; }这个代码能解决这个问题吗
时间: 2023-12-09 22:06:27 浏览: 70
SeqList.h #include <stdio.h> //包含标准输入输出流的头文件 #include <assert.h
这段代码实现的是贪心策略,但是它存在一些问题,可能不能解决这个问题。以下是代码的问题:
1. 排序方法不正确:代码使用了冒泡排序的方法对金币按照单位价值从大到小进行排序,但是排序方法不正确,应该使用快速排序(`qsort`)等时间复杂度更低的排序方法。
2. 只考虑了整数重量:代码使用了一个循环将每个金币的重量全部填满,没有考虑到金币可以分割的情况。应该将金币按照单位重量从大到小依次装入背包,直到背包无法再装下更多的金币为止。
3. 精度问题:代码使用了`double`类型来存储单位价值和最大价值,但是在计算过程中可能存在精度丢失的问题。
因此,如果没有对代码进行改进,可能无法正确地解决这个问题。
阅读全文