网易内部开了一家水果店,最近推出了一个水果礼盒的产品。礼盒总的目标重量是固定的,水果店的工人需要从N个不同重量的水果中,挑选出合适的一些水果,使尽量装满这个礼盒。但是礼盒比较脆弱,所以水果的重量总和不能超过礼盒的目标重量。
问每一次工人装水果的时候,这个礼盒最多能装多少。
第一行为水果礼盒的目标重量C,为一个正整数,0<C<=100000第二行为所有可选水果的重量数组W,都为整数,用空格分隔,每个值不大于1000,0<length(W)<=10000
一个整数,礼盒最多能够装多少重量的水果
100 47 59 42
89
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int C = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().split(" "); int n = strArr.length; int[] weights = new int[n]; int sum = 0; for(int i = 0; i < n; i++){ weights[i] = Integer.parseInt(strArr[i]); sum += weights[i]; } // 求解背包问题 int[] dp = new int[sum + 1]; dp[0] = 1; dp[sum] = 1; for(int i = 0; i < n; i++){ dp[weights[i]] = 1; for(int j = 0; j <= sum; j++){ if(dp[j] == 1 && j - weights[i] >= 0) dp[j - weights[i]] = 1; } } // 降序依次检测满足要求的重量哪个最大 for(int weight = sum; weight >= 0; weight--){ if(dp[weight] == 1 && weight <= C){ System.out.println(weight); break; } } } }当然,直接求解背包问题也是可以的
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int C = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().split(" "); int n = strArr.length; int[] weights = new int[n]; int sum = 0; for(int i = 0; i < n; i++) weights[i] = Integer.parseInt(strArr[i]); // 求解背包问题 int[] dp = new int[C + 1]; for(int i = 0; i < n; i++){ for(int j = C; j >= 0; j--){ if(j >= weights[i]) dp[j] = Math.max(dp[j], dp[j - weights[i]] + weights[i]); else break; } } System.out.println(dp[C]); } }