风机离升压站的距离,如 30 20 35 40
风机发电量,如 20 18 25 30
输电总距离的限制,如50
输送电量的最大值
30 20 35 40 20 18 25 30 50
38
距离,发电量,总距离各起一行,数组间以空格分隔
普通背包问题(我被这个输入搞死
#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; }
#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; }
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); } } }
#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; }
#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; }
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]);
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])
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]; } }
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])
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]);
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))
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])
/* * 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语言的
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) } }
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); } }
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]; } }