Java(javac 1.8) 解法, 执行用时: 98ms, 内存消耗: 24692K, 提交时间: 2020-08-09 14:12:14

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int w = scan.nextInt();
        int wt[] = new int[n];
        int val[] = new int[n];
        for (int i = 0; i < n; i++) {
            wt[i] = scan.nextInt();
            val[i] = scan.nextInt();
        }
        float res = 0f;
        int dp[][] = new int[n + 1][10000 + 2];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 10001; j++) {
                if (j < wt[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wt[i - 1]] + val[i - 1]);
                    if (j >= w) {
                        res = Math.max(res, (float)dp[i][j] / (float)j);
                    }
                }
            }
        }
        System.out.println((int)(res * 1000));
    }
}

C++14(g++5.4) 解法, 执行用时: 352ms, 内存消耗: 4448K, 提交时间: 2020-05-13 12:54:33

#include<bits/stdc++.h>
typedef long long ll;

using namespace std;

#define Init1 ios::sync_with_stdio(false)
#define Init2 cin.tie(0)
#define INF 0x3f3f3f3f

const int N = 255;
const int M = 1e6 + 105;
int w[N], t[N];

int dp[M];
int main(){
    Init1; Init2;
    int n, W;
    cin>>n>>W;
    for(int i = 1; i <= n; ++i) 
        cin>>w[i]>>t[i];
    for(int i = 1; i <= n; ++i){
        for(int j = M - 1; j >= w[i]; --j){
            dp[j] = max(dp[j - w[i]] + t[i], dp[j]);
        }
    }
    double ans = 0;
    for(int i = W; i < M; ++i){
        ans = max(ans, 1.0*dp[i] / i);
        // cout<<dp[i]<<endl;
    }
    cout<<int(ans*1000)<<endl;
    // system("pause");
}

C++11(clang++ 3.9) 解法, 执行用时: 83ms, 内存消耗: 2408K, 提交时间: 2020-05-13 12:20:49

#include<stdio.h>
#include<math.h>
#define ll long long
#define N 250000
#define inf 0x3f3f3f3f

double max(double x,double y);
double max(double x,double y)
{ if(x>y) y=x;return y; }

int main()
{
	int i,j;
	double ans=0;
	int n,W;					//n名学生,限制最小总体重W 
	double f[N+1];				//f[x]:总重恰为x时的最大力量 
	scanf("%d%d",&n,&W);
	int w[n+1],p[n+1];			//weight&&power
	for(i=1;i<=N;i++)	f[i]=0; f[0]=0;
	for(i=1;i<=n;i++)   scanf("%d%d",&w[i],&p[i]);
	for(i=1;i<=n;i++)
		for(j=N;j>=w[i];j--)
			f[j]=max( f[j] , f[j-w[i]]+p[i] );
	
	for(i=W;i<=N;i++)
	{
		ans=max(ans,f[i]/i);
	}
	printf( "%d\n",(int)(1000*ans) );
	return 0;
}