首页 > 试题广场 >

风电场风机发电调度问题

[编程题]风电场风机发电调度问题

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

某风电场每台风机的发电量和距离升压站的距离各不相同，如风机1：发电量30，距离20；风机2：发电量35，距离25；风机3：发电量25，距离18……，要求在输电总距离限定（如小于100）的前提下，选择风机向升压站输电，使得输送的电量最大。

输入描述:

风机离升压站的距离，如 30 20 35 40

风机发电量，如 20 18 25 30

输电总距离的限制，如50

输出描述:

输送电量的最大值

示例1

输入

30 20 35 40
20 18 25 30
50

输出

说明

距离，发电量，总距离各起一行，数组间以空格分隔

算法知识视频讲解

牛客685342718号

普通背包问题（我被这个输入搞死

#include 
#include 
using namespace std;
int main(){
    vector values,costs;
    int limits;
    int num;
    while(cin >> num){
        costs.push_back(num);
        if(cin.get()=='\n') break;
    }
    while(cin >> num){
        values.push_back(num);
        if(cin.get()=='\n') break;
    }
    cin >> limits;
    int n=costs.size();
    vector> dp(n,vector(limits+1,0));
    for(int i=0; i<n; i++){
        for(int j=0; j<limits+1; j++){
            if(i==0){
                if(j-costs[i]>=0){
                    dp[i][j]=values[i];
                }
                continue;
            }
            if(j-costs[i]>=0){
                dp[i][j]=max(dp[i-1][j],values[i]+dp[i-1][j-costs[i]]);
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout<< dp[n-1][limits] << endl;
    return 0;
}

发表于 2021-03-03 10:58:36 回复(0)

loveling

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
 
int max(int p,int q)
{
    return p>q?p:q;
}
 
int main()
{
    vector<int> v;
    int m=0,n=0,*dp,p,q;
    while(scanf("%d",&m)!=EOF)
        v.push_back(m);
    m = v.size()/2;
    n = v[v.size()-1];
    dp = new int[2*n+2]{0};
    for(int i=0;i<m;i++)
    {
        int p = i%2,q = p?0:1;
        for(int j=0;j<=n;j++)
        {
            if(j>=v[i])
                dp[p*(n+1)+j]=max(dp[q*(n+1)+j],dp[q*(n+1)+j-v[i]]+v[m+i]);
            else
                dp[p*(n+1)+j] = dp[q*(n+1)+j];
        }
    }
    cout<<dp[((m-1)%2)*(n+1)+n]<<endl;
    delete dp;
    return 0;
}

发表于 2021-03-02 11:33:06 回复(0)

牛客166804111号

暴力查找，用temp记录最小

import java.util.*;
 public class Main{
     public static void main(String[] args){
         Scanner sc = new Scanner(System.in);
         while(sc.hasNext()){
             String[] arr1 = sc.nextLine().split(" ");
             String[] arr2 = sc.nextLine().split(" ");
             int max = sc.nextInt();
             int answer=0;
             for(int i=0;i<arr1.length;i++){
                 for(int j=i+1;j<arr1.length;j++){
                     int sum = Integer.parseInt(arr1[i])+Integer.parseInt(arr1[j]);
                     int temp = Integer.parseInt(arr2[i])+Integer.parseInt(arr2[j]);
                     if(answer<temp&&sum<=max){
                         answer=temp;
                     }
                 }
             }
             System.out.println(answer);
         }
     }
 }

发表于 2022-04-19 22:53:03 回复(0)

康斯坦丁_s

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main(){
    vector<int> values,costs;
    int limits;
    int num;
    while(cin >> num){
        costs.push_back(num);
        if(getchar()=='\n') break;
    }
    while(cin >> num){
        values.push_back(num);
        if(cin.get()=='\n') break;
    }
    cin >> limits;
    int n=costs.size();
    int dp[10000];
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=limits;j>=costs[i];j--)
        {
            dp[j]=max(dp[j],dp[j-costs[i]]+values[i]);
        }
    }
    cout<<dp[limits];
    return 0;
}

编辑于 2021-05-13 11:24:42 回复(0)

牛客399552483号

#include <iostream>
#include <vector>
#include<string>
#include<cmath>
using namespace std;

void solve(int i, vector<int> vec1 ,int n,vector<int> &ok,vector<int> vec2, int limit)
{
	int sum1 = 0;
	int sum2 = 0;
	int k = n - 1;
	
	vector<int>vec4;
	while (i > 0)
	{
		if (i & 1)
		{
			
			vec4.push_back(k);
		}
		k--;
		i >>= 1;
	}
	
	for (auto it = vec4.begin(); it != vec4.end(); it++)
	{
		sum1 += vec1[*it];
		sum2 += vec2[*it];
	}
	if (sum1 <= limit)
	{
		ok.push_back(sum2);
	}
}
int main()
{
	vector<int> vec1;
	vector<int> vec2;
	vector<int> ok;
	
	int a;
	int limit;
	while ((cin >> a) )
	{
		vec1.push_back(a);
		if (cin.get() == '\n')
		{
			break;
		}
	}

	while ((cin >> a))
	{
		vec2.push_back(a);
		if (cin.get() == '\n')
		{
			break;
		}

	}
	
	cin >> limit;
	
	//假设容器vec1中有n个元素，每个元素按照有和没有在组合中 两种状态，有就是1，没有就是0.那么所有排列组合按照二进制排列一共有2^n种，用十进制数表示就是0到2^n -1
	//将0到2^n -1中的数分别循环地与1进行位与操作，如果结果不为0，说明当前这个数的二进制位最右边的位为1，否则为0；如果为1则将数组对应的最右边的元素提取出来，等待后续的相加。如果为0，则无操作，
	//接着将当前数右移一位。回到循环处，循环条件为当前这个数大于0，因为如果等于0了，说明此时没有任何数组中的元素在组合之中了。
	int i = 1;
	
	for (i = 1; i < pow(2, vec1.size()); i++)
	{
		solve(i, vec1, vec1.size(), ok, vec2, limit);
	}
	//对ok容器做排序
	for (int i = 1; i <= ok.size()-1; i++)
	{
		for (int j = 1; j <= ok.size() - i; j++)
		{
			if (ok[j - 1]>ok[j])
			{
				int tmp = ok[j - 1];
				ok[j - 1] = ok[j];
				ok[j] = tmp;

			}
		}
	}
	cout << ok[ok.size() - 1] << endl;
	return 0;
}

编辑于 2021-09-12 14:37:07 回复(0)

暖暖1997

let arr1 = readline().split(' '); // i
let arr2 = readline().split(' '); 
let distanceMax = parseInt(readline()); // j

let distanceArr = arr1.map(Number);
let powerArr = arr2.map(Number);
let dp = new Array();
for(let i = 0 ; i< distanceArr.length ;i++){
    dp[i] = new Array();
    for(let j = 0; j < distanceMax+1 ;j++){ 
        if(i==0){
            if(distanceArr[i]<=j){
                dp[i][j] = powerArr[i];
            }else{
                dp[i][j] = 0; //最坑的点在于我忘记初始化 磨了好久
            }
            continue;
        }
        if(distanceArr[i]<=j){          
            dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-distanceArr[i]]+powerArr[i]);
        }else{
            dp[i][j]= dp[i-1][j];
        }
    }
}
console.log(dp[distanceArr.length-1][distanceMax]);

发表于 2021-09-06 23:07:53 回复(0)

imcl

0-1背包

cost = map(int, raw_input().strip().split(' '))
value = map(int, raw_input().strip().split(' '))
N = input() 

dp = [[0] * (N + 1) for _ in range(len(cost)+1)]

for i in range(1, len(cost)+1):
    for j in range(1, N+1):
        if j < cost[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i-1]]+value[i-1])
            
print(dp[-1][-1])

发表于 2021-07-05 15:22:09 回复(0)

小目标来个offer

难受的输入！！！

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String diStr = scanner.nextLine();
        String[] Str1 = diStr.split(" ");
        String vaStr = scanner.nextLine();
        String[] Str2 = vaStr.split(" ");
        
        int[] dist = new int[ Str1.length] ;
        int[] value = new int[ Str1.length];
        int maxDis;
        
        for (int i = 0; i < Str1.length; i++) {
            dist[i] = Integer.parseInt(Str1[i]);
            value[i] = Integer.parseInt(Str2[i]);
        }

        maxDis = scanner.nextInt();

        System.out.println(test2(dist, value, maxDis));
    }
    public static int test2(int[] dist, int[] value, int maxDis) {
        int[] dp = new int[maxDis + 1];

        for (int i = 0; i < dp.length; i++) {
            if (i >= dist[0]) {
                dp[i] = value[0];
            }
        }

        for (int i = 1; i < dist.length; i++) {
            for (int j = maxDis; j >= dist[i];j--) {
                dp[j] = Math.max(dp[j], value[i] + dp[j - dist[i]]);
            }
        }

        return dp[maxDis];
    }
}

发表于 2021-06-19 20:01:31 回复(0)

TensorBi

经典背包问题，建议先了解了解这个问题。

有n件东西要放进背包中，每个东西有重量和体积，要求在总重量的限制下体积尽可能的大

利用动态规划

现将物品按重量从小到大排序

首先分两种情况:1、背包的最大可放重量小于当前物品的重量，则背包可放物品的最大重量为前n-1件物品的最大重量

2、背包的最大可放重量大于当前物品的重量；这是又要分两种情况，放还是不放当前物品，

2.1：不放当前物品，则背包可放物品的最大重量为前n-1件物品的最大重量

2.2：放当前物品，那就计算背包在放了放了当前物品后还能放多重的物品，按照这个重量找体积最大的放物体的方法，比较2.1和2.2的体积，那个大选哪个

js的代码如下

let distanceArr = readline().split(' ').sort((a,b)=> {return a-b})
    let powerArr = readline().split(' ').sort((a,b)=> {return a-b})
    let maxDis = parseInt(readline())
    let n = distanceArr.length
    let dp = Array.from(new Array(n+1),()=>new Array(maxDis+1).fill(0))
    for (let i=1;i<=n;i++) {
        for (let j=1;j<=maxDis;j++) {
            if (distanceArr[i-1]>j) {
                dp[i][j] = dp[i-1][j]
            }
            else {
                dp[i][j] = Math.max(
                dp[i-1][j],
                parseInt(powerArr[i-1]) + dp[i-1][j-distanceArr[i-1]]
                )
            }
        }
    }
    console.log(dp[n][maxDis])

发表于 2021-04-27 10:47:20 回复(0)

xhxhsadsf

if(line=readline()){
    var lines = line.split(' ');
    var a = parseInt(lines[0]);
    var b = parseInt(lines[1]);
    var c = parseInt(lines[2]);
    var d = parseInt(lines[3]);
}
let distance=[a,b,c,d];
if(line=readline()){
    var lines = line.split(' ');
    var e = parseInt(lines[0]);
    var f = parseInt(lines[1]);
    var g = parseInt(lines[2]);
    var h = parseInt(lines[3]);
}
let power=[e,f,g,h];
if(line=readline()){
    var lines = line.split(' ');
    var i = parseInt(lines[0]);
}
let MechineNum=power.length;
let restrict=i;

//let memo=new Array(MechineNum).fill(new Array(restrict).fill(0)); 
//因为fill是引用赋值所以第一个new Array传入的是同一个地址
//可以用下面的map循环创建
let memo=(new Array(MechineNum)).fill(0).map(() => (new Array(restrict)).fill(0))
for(let MN=0;MN<MechineNum;MN++){
    for(let Dis=0;Dis<=restrict;Dis++){
        if(MN==0){
            if(Dis-distance[MN]>=0){
                memo[MN][Dis]=power[MN];
            }
            continue;
        }
        if(Dis-distance[MN]>=0){
            memo[MN][Dis]=Math.max(memo[MN-1][Dis],power[MN]+memo[MN-1][Dis-distance[MN]]);
        }
        else{
             memo[MN][Dis]=memo[MN-1][Dis];
        }
    }
}

print(memo[MechineNum-1][restrict]);

编辑于 2021-03-19 16:16:04 回复(0)

Python

牛客241206516号

A=[int(i) for i in ('0 '+input().strip()).split()]

B=[int(i) for i in ('0 '+input().strip()).split()]

n=int(input().strip())

C=[]

for i in range(len(A)):

for j in range(len(A)):

for k in range(len(A)):

for l in range(len(A)):

if A[i]+A[j]+A[k]+A[l] <=n:

C.append(B[i]+B[j]+B[k]+B[l])

print(max(C))

发表于 2021-03-18 15:43:18 回复(0)

牛客856254075号

参考 https://www.cnblogs.com/kkbill/p/12081172.html

distances = list(map(int, input().split()))
powers = list(map(int, input().split()))
total = int(input())

array = [0] * total
dp = []

for i in distances:
    dp.append(array.copy())

for i in range(len(powers)):
    for k in range(total):
        if k + 1 >= distances[i]:
            power_with_i = dp[i - 1][k + 1 - distances[i]] + powers[i]
        else:
            power_with_i = 0
        power_without_i = dp[i - 1][k]
        dp[i][k] = max(power_with_i, power_without_i)

print(dp[len(powers) - 1][total - 1])

发表于 2021-03-15 17:41:13 回复(0)

C/C++

刺客201803262223612

/*
* 31题 风电场风机发电问题 代码存档
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    char str1[1000];
    char str2[1000];
    int *weight, *value, *dp;
    int num = 0, limit;
    //scanf("%d%d", &num, &limit);

    weight = (int*) malloc(1000 * sizeof(int));
    value = (int*) malloc(1000 * sizeof(int));
    dp = (int*) malloc( 1000 * sizeof(int));
    
    //输入数据
    int *input_data = (int*) malloc(1000 * sizeof(int));
    int cnt = 0;
    while (scanf("%d", &input_data[cnt]) != EOF)
    {
        cnt++;
    }
    num = cnt / 2;
    for (int i = 0; i < num; i++)
        weight[i] = input_data[i];
    for (int i = num; i < cnt - 1; i++)
        value[i - num] = input_data[i];
    
    limit = input_data[cnt - 1];
    //printf("%d %d\n", num, limit);
    
    for (int i = 0; i < limit; i++)
    {
        dp[i] = 0;
    }
    
    for (int i = 0; i < num; i++)
    {
        for (int v = limit; v >= weight[i]; v--)
        {
            dp[v] = max(dp[v], dp[v - weight[i] ] + value[i]);
        }
    }
    
    int max_value = 0;
    for (int i = 0; i <= limit; i++)
    {
        max_value = max_value < dp[i] ? dp[i] : max_value;
    }
    printf("%d\n", max_value);
    return 0;
}

来个C语言的

发表于 2021-03-15 15:15:55 回复(0)

二三维

import scala.io._

object getElectrics {

  def getElectricsMax(windDistance: Array[Int], windEle: Array[Int], distanceLimit: Int) : Int= {
    var max = 0

    for (i <- 0 to windEle.length -1; j <- i + 1 to windEle.length-1) {
      if (windDistance(i) + windDistance(j) <= distanceLimit) {
        max = if(windEle(i)+windEle(j) > max) windEle(i)+windEle(j) else max
      }
    }
    max
  }

  def main(args: Array[String]): Unit = {
    val windDistance = StdIn.readLine().split(' ').map(e => e.toInt)
    val windEle = StdIn.readLine().split(' ').map(e => e.toInt)
    val distanceLimit = StdIn.readInt()
    val e =getElectricsMax(windDistance, windEle, distanceLimit)
    println(e)
  }

}

发表于 2021-03-13 23:39:12 回复(0)

牛客884264861号

public class Main （）{
     public static void getEle(int[] eleList,int[] lenList,int maxLen){
        int len = lenList.length;
        int cando = 0;
        int maxEle = 0;
        int mLen = 0;
        int c = 0;
        for (int i = 0; i < len; i++) {

            if(lenList[i] <= maxLen){

                int bufEle = eleList[i];
                cando = lenList[i];
                for (int j = i+1; j < len; j++) {
                    int maxMus = getMaxLen(cando,lenList[j],maxLen);
                    if(maxMus > 0){
                        cando = maxMus;
                        bufEle += eleList[j];
                    }
                }
                if(mLen < cando){
                    mLen = cando;
                }
                if(maxEle < bufEle){
                    maxEle = bufEle;
                }
            }
        }
        System.out.println("最大电量："+maxEle);
        System.out.println("最大距离："+mLen);
    }
    public static Integer getMaxLen(int initMus,int addMus,int maxLen){
        int rLen = initMus+addMus;
        if(rLen <= maxLen){
            return rLen;
        }else{
            return 0;
        }
    }

    public static void main(String[] args) {
        int[] eleList = {20, 18, 20, 25, 30};
        int[] lenList = {30, 10, 5, 35, 40};
        int maxLen = 50;
        getEle(eleList,lenList,maxLen);
    }
}

发表于 2021-03-12 14:15:05 回复(0)

Java

foobarbazqux

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    /**
     * 链接：https://www.nowcoder.com/questionTerminal/dee7a45562324d9a8e2bc7f0e4465bfc
     * [编程题]风电场风机发电调度问题
     * <p>
     * 某风电场每台风机的发电量和距离升压站的距离各不相同，
     * <p>
     * 如风机1：发电量30，距离20；风机2：发电量35，距离25；风机3：发电量25，距离18……，
     * <p>
     * 要求在输电总距离限定（如小于100）的前提下，选择风机向升压站输电，使得输送的电量最大。
     */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        List<List<Integer>> data = new ArrayList<>();
        while (input.hasNextLine()) {
            String line = input.nextLine();
            String[] values = line.split(" ");
            List<Integer> lineData = new ArrayList<>();
            for (String value : values) {
                lineData.add(Integer.valueOf(value));
            }
            data.add(lineData);
        }

        List<Integer> distances = data.get(0);
        List<Integer> powers = data.get(1);
        int maxDist = data.get(2).get(0);
        Main s = new Main();
        System.out.println(s.getMaxResult(distances, powers, maxDist));
    }

    private int getMaxResult(List<Integer> distances, List<Integer> powers, int maxDist) {
        if (distances.size() == 0 || maxDist == 0) return 0;
        int[][] dp = new int[distances.size()][maxDist + 1];

        for (int i = 0; i < dp.length; i++) {
            int dist = distances.get(i);
            int power = powers.get(i);
            for (int j = 0; j <= maxDist; j++) {
                if (dist <= j) {
                    if (i == 0) {
                        dp[i][j] = power;
                    } else {
                        dp[i][j] = Integer.max(dp[i - 1][j - dist] + power, dp[i - 1][j]);
                    }
                } else {
                    if (i > 0) {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }

        }
        return dp[dp.length - 1][maxDist];
    }


}

发表于 2021-03-11 16:49:27 回复(0)

5sy

str=input().strip()
A=[int(i) for i in str.split(" ")] 
str=input().strip()
B=[int(i) for i in str.split(" ")]
n=int(input().strip())
C=[]
for i in range(len(A)):
    for j in range(i+1,len(A)):
        if A[i]+A[j] <=n:
            C.append(B[i]+B[j])
print(max(C))

发表于 2021-03-09 17:41:03 回复(0)