首页 > 试题广场 >

最多的水果

[编程题]最多的水果
  • 热度指数:428 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
网易内部开了一家水果店,最近推出了一个水果礼盒的产品。礼盒总的目标重量是固定的,水果店的工人需要从N个不同重量的水果中,挑选出合适的一些水果,使尽量装满这个礼盒。但是礼盒比较脆弱,所以水果的重量总和不能超过礼盒的目标重量。

问每一次工人装水果的时候,这个礼盒最多能装多少。

输入描述:
第一行为水果礼盒的目标重量C,为一个正整数,0<C<=100000
第二行为所有可选水果的重量数组W,都为整数,用空格分隔,每个值不大于1000,0<length(W)<=10000


输出描述:
一个整数,礼盒最多能够装多少重量的水果
示例1

输入

100
47 59 42

输出

89
和2021年网易笔试题中那道“小易的考试成绩”的思路如出一辙,都是先求解01背包问题,然后降序遍历能得到的重量并输出最大的。但这个方法我在使用python的时候会超时。
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]);
    }
}



编辑于 2021-01-18 15:21:36 回复(0)
#include<vector>
#include<iostream>
using namespace std;
int main(){
    int n;
    vector<int> a;
    cin>>n;
    int num=0;
    while(1){
      num++;
      int temp;
      cin>>temp;
      a.push_back(temp);
      if(cin.get()=='\n') break;
  }
    vector<int> dp(n+1,0);
    for(int i=0;i<num;i++){
        for(int j=n;j>0;j--){
            if(j>=a[i]) dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
            else break;
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

编辑于 2021-01-18 15:11:06 回复(0)