镇江百度网站建设,北京网络营销咨询公司,南宁手机平台网站,做公司网站每年多少钱某个充电站#xff0c;可提供n个充电设备#xff0c;每个充电设备均有对应的输出功率。任意个充电设备组合的输出功率总和#xff0c;均构成功率集合P的1个元素。功率集合P的最优元素#xff0c;表示最接近充电站最大输出功率P_max的元素 输入描述 输入为3行: 第1行为充电设…某个充电站可提供n个充电设备每个充电设备均有对应的输出功率。任意个充电设备组合的输出功率总和均构成功率集合P的1个元素。功率集合P的最优元素表示最接近充电站最大输出功率P_max的元素 输入描述 输入为3行: 第1行为充电设备个数n 第2行为每个充电设备的输出功率P_i 第3行为充电站最大输出功率P_max
输出描述 功率集合P的最优元素 备注 充电设备个数 n 0 最优元素必须小于或等于充电站最大输出功率P_max 示例1
输入
4 50 20 20 60
90 输出
90 说明 当充电设备输出功率50、20、20组合时其输出功率总和为90最接近充电站最大充电输出功率因此最优元素为90。
示例2
2 50 40
30 输出 0 说明 所有充电设备的输出功率组合均大于充电站最大充电输出功率30此时最优元素值为0。
Java 代码
import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;
import java.math.BigInteger;
import java.util.stream.Stream;class Main {public static void main(String[] args) {// 处理输入Scanner in new Scanner(System.in);int n in.nextInt();in.nextLine();Integer[] p Arrays.stream(in.nextLine().split( )).map(Integer::parseInt).toArray(Integer[]::new);int p_max in.nextInt();//dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。int[][] dp new int[n 1][p_max 1];// 初始化, i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。for (int j p_max; j p[0]; j--) {dp[0][j] dp[0][j - p[0]] p[0];}for (int i 1; i n; i) { // 遍历物品for (int j 0; j p_max; j) { // 遍历背包容量// 背包容量为j如果物品i的体积此时dp[i][j]就是dp[i - 1][j]if (j p[i]) {dp[i][j] dp[i - 1][j];} else {dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - p[i]] p[i]);}}}System.out.println(dp[n-1][p_max]);}}Python代码
import functools
import sys
from collections import Counter, defaultdict
import copy
from itertools import permutations
import re
import math
import sys#处理输入
n int(input())
p [int(x) for x in input().split( )]
p_max int(input())#dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
dp [[0 for x in range(p_max 1)] for y in range(n1)]# 初始化, i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。
j p_max
while(j p[0]):dp[0][j] dp[0][j - p[0]] p[0]j - 1for i in range(1, n): # 遍历物品for j in range(0, p_max1): # 遍历背包容量# 背包容量为j如果物品i的体积此时dp[i][j]就是dp[i - 1][j]if (j p[i]):dp[i][j] dp[i - 1][j]else:dp[i][j] max(dp[i - 1][j], dp[i - 1][j - p[i]] p[i])print(dp[n-1][p_max])
JS代码
function main(n,p,p_max) {//dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。let dp new Array(n1)for (let i0;in1;i) {dp[i] new Array(p_max1).fill(0)}// 初始化, i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。let j p_maxwhile(j p[0]){dp[0][j] dp[0][j - p[0]] p[0]j - 1}for (let i1;in;i){ // 遍历物品for (let j0;jp_max1;j) { // 遍历背包容量// 背包容量为j如果物品i的体积此时dp[i][j]就是dp[i - 1][j]if (j p[i])dp[i][j] dp[i - 1][j]elsedp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - p[i]] p[i])}}console.log(dp[n-1][p_max])}main(4,[50, 20, 20, 60],90)
