牛牛炒股票

[编程题]牛牛炒股票

热度指数：632 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛得知了一些股票今天买入的价格和明天卖出的价格，他找犇犇老师借了一笔钱，现在他想知道他最多能赚多少钱。

输入描述:

每个输入包含一个测试用例。
输入的第一行包括两个正整数,表示股票的种数N(1<=N<=1000)和牛牛借的钱数M(1<=M<=1000)。
接下来N行，每行包含两个正整数，表示这只股票每一股的买入价X(1<=X<=1000)和卖出价Y(1<=Y<=2000)。
每只股票可以买入多股，但必须是整数。

输出描述:

输出一个整数表示牛牛最多能赚的钱数。

示例1

输入

输出

算法知识视频讲解

麦垛上的守望者

本地测试没问题，但是牛客测试，每次都提醒语法错误或者数组越界，就是给items数组赋值那一块，不知道为什么

public class Main {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();

int[][] items = new int[n][2]; //股票价格
//int[] values = new int[n]; //收益

for(int i=0;i<n;i++){
// items[i][0] = Integer.parseInt(scanner.next());
// items[i][1] = Integer.parseInt(scanner.next());
items[i][0] = scanner.nextInt();
items[i][1] = scanner.nextInt();
items[i][1]=items[i][1]-items[i][0];
//values[i] = scanner.nextInt()-items[i];
scanner.nextLine();
}

int[] dp = new int[m+1];
for(int i=0;i<n;i++){
for(int j=items[i][0];j<=m;j++){
dp[j] = Math.max(dp[j], dp[j-items[i][0]]+items[i][1]);
}
}

//System.out.println(dp[m-1]);
System.out.println(dp[m]);

scanner.close();
}

}

编辑于 2018-05-25 17:01:02 回复(3)

Dracary

完全背包。

但牛客的输入数据有问题，有时候不足n行，要加个判断

import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
if(n>0 && m>0){
int[] buy = new int[n];
int[] sale = new int[n];
int[] f = new int[m+1];
for(int i = 0; i < n && sc.hasNext(); i++){
buy[i] = sc.nextInt();
sale[i] = sc.nextInt();
}
for(int i=0;i < n;i++){
for(int j=buy[i];j<f.length;j++) {
f[j] = Math.max(f[j], f[j - buy[i]] + sale[i] - buy[i]);
}
}
System.out.println(f[m]);
}
}
}

发表于 2019-02-23 16:59:46 回复(0)

Deep_Blue


	
	
		#include <iostream>
	

	
		#include <vector>
	

	
		usingnamespacestd;
	

	
		 
	

	
		intmain()
	

	
		{
	

	
		   vector<int> cost;
	

	
		   vector<int> profit;
	

	
		    intN, M;
	

	
		    while(cin>>N>>M)
	

	
		    {
	

	
		    for(inti = 0; i < N; i++)
	

	
		    {
	

	
		       intin, out;
	

	
		       cin>>in>>out;
	

	
		       cost.push_back(in);
	

	
		       profit.push_back(out - in);
	

	
		    }
	

	
		 
	

	
		    vector<vector<int>> maxprofit(N, vector<int>(M + 1, 0));
	

	
		    for(inti = 0; i < N; i++)
	

	
		    {
	

	
		       maxprofit[i][0] = 0;
	

	
		    }
	

	
		    for(intj = 1; j <= M; j++)
	

	
		    {
	

	
		       if(j >= cost[0])
	

	
		       {
	

	
		          maxprofit[0][j] = maxprofit[0][j - cost[0]] + profit[0];
	

	
		       }
	

	
		    }
	

	
		    for(inti = 1; i < N; i++)
	

	
		    {
	

	
		       for(intj = 0; j <= M; j++)
	

	
		       {
	

	
		          maxprofit[i][j] = maxprofit[i - 1][j];
	

	
		          if(j >= cost[i] && maxprofit[i][j - cost[i]] + profit[i] > maxprofit[i][j])
	

	
		            maxprofit[i][j] = maxprofit[i][j - cost[i]] + profit[i];
	

	
		       }
	

	
		 
	

	
		    }
	

	
		    if(maxprofit[N - 1][M] >= 0)
	

	
		    cout<<maxprofit[N - 1][M]<<endl;
	

	
		    else
	

	
		      cout<<0<<endl;
	

	
		    cost.clear();
	

	
		    profit.clear();
	

	
		    }
	

	
		    return0;
	

	
		}