某個(gè)充電站，可提供n個(gè)充電設(shè)備，每個(gè)充電設(shè)備均有對(duì)應(yīng)的輸出功率。任意個(gè)充電設(shè)備組合的輸出功率總和，均構(gòu)成功率集合P的1個(gè)元素。功率集合P的最優(yōu)元素，表示最接近充電站最大輸出功率P_max的元素
輸入描述
輸入為3行:
第1行為充電設(shè)備個(gè)數(shù)n
第2行為每個(gè)充電設(shè)備的輸出功率P_i
第3行為充電站最大輸出功率P_max

輸出描述
功率集合P的最優(yōu)元素
備注
充電設(shè)備個(gè)數(shù) n >0
最優(yōu)元素必須小于或等于充電站最大輸出功率P_max
示例1：

輸入

4
50 20 20 60

90
輸出

90
說(shuō)明
當(dāng)充電設(shè)備輸出功率50、20、20組合時(shí)，其輸出功率總和為90，最接近充電站最大充電輸出功率，因此最優(yōu)元素為90。

示例2：

2
50 40

30
輸出
0
說(shuō)明
所有充電設(shè)備的輸出功率組合，均大于充電站最大充電輸出功率30，此時(shí)最優(yōu)元素值為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] 表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。int[][] dp = new int[n + 1][p_max + 1];// 初始化, i為0，存放編號(hào)0的物品的時(shí)候，各個(gè)容量的背包所能存放的最大價(jià)值。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的體積，此時(shí)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] 表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。
dp = [[0 for x in range(p_max + 1)] for y in range(n+1)]# 初始化, i為0，存放編號(hào)0的物品的時(shí)候，各個(gè)容量的背包所能存放的最大價(jià)值。
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_max+1): # 遍歷背包容量# 背包容量為j，如果物品i的體積，此時(shí)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] 表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。let dp = new Array(n+1)for (let i=0;i<n+1;i++) {dp[i] = new Array(p_max+1).fill(0)}// 初始化, i為0，存放編號(hào)0的物品的時(shí)候，各個(gè)容量的背包所能存放的最大價(jià)值。let j = p_maxwhile(j >= p[0]){dp[0][j] = dp[0][j - p[0]] + p[0]j -= 1}for (let i=1;i<n;i++){  // 遍歷物品for (let j=0;j<p_max+1;j++) { // 遍歷背包容量// 背包容量為j，如果物品i的體積，此時(shí)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)