问题 4116 --分数背包(完善程序)

4116: 分数背包(完善程序)★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 74  解决: 44
[提交][状态][命题人:]

题目描述


#include<cstdio>
using namespace std;

const int maxn=1005;

int n,B,w[maxn],v[maxn];

int gcd(int u,int v){
	if(v==0)
	return u;
	return gcd(v,u%v);
}

void print(int w,int v){
	int d=gcd(w,v);
	w=w/d;
	v=v/d;
	if(v==1)
	printf("%d\n",w);
	else
	printf("%d/%d\n",w,v);
}

void swap(int &x, int &y){
	int t=x; x=y; y=t;
}

int main( ){
	scanf("%d %d",&n,&B);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&w[i],&v[i]);
	}
	for(int i=1;i<n;i++)
		for(int j=1;j<n;j++)
			if(____(1)_____){
				swap(w[j],w[j+1]);
				swap(v[j],v[j+1]);
			}
	int curV,curW;
	if(____(2)_____){
		_____(3)_____
	}else{
		print(B*w[1],v[1]);
		return 0;
	}
	
	for(int i=2;i<=n;i++)
		if(curV+v[i]<=B){
			curV+=v[i];
			curW+=w[i];
		}else{
			print(_____(4)____);
			return 0;
		}
	print(_____(5)_____);
    return 0;
}

输入

输出

样例输入
Copy
3 8
4 5
4 3
2 2
样例输出
Copy
42/5

提示

来源

[提交][状态]