首页 > 试题广场 >

资产包打包

[编程题]资产包打包
  • 热度指数：3385 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
在金融资产交易中，经常涉及到资产包的挑选打包。在资产包打包过程中，每种类型的资产有固定的数量与价值，需选择某几种资产打包，使得资产包总价值最大。打包时每种资产只能整体打包，不能分割。假设现有可容纳M条资产的资产包，另外有N种资产。资产Na数量为Ta条，总价值为Va元；资产Nb数量为Tb条，总价值为Vb元；资产Nc数量为Tc条，总价值为Vc元......；资产Nn数量为Tn，总价值为Vn。编写算法，挑选哪些类型资产放入资产包可使得资产包总价值最大？

输入描述:
资产总量,资产种类,每类资产条数,每类资产价值(逗号分隔)；其中每类资产条数与每类资产价值为空格分隔。
总格式如下：
资产总量,资产种类,资产A条数 资产B条数 资产C条数,资产A价值 资产B价值 资产C价值！
举例，资产总量为12，资产种类3种，3种资产条数分别为4，5，7，三种资产价值分别是500元，600元，800元，输入如下：
12,3,4 5 7,500 600 800
资产总量和资产种类都不超过1000，资产条数不超过1000，资产价值不超过10000，所有数值均为正整数。


输出描述:
资产包中资产最大总价值
示例1

输入

12,3,4 5 7,500 600 800

输出

1400
算法知识视频讲解
添加回答
Java
北极以北_头像 北极以北_
经典01背包模板，可用一维dp数组优化，这里遍历重量的时候必须逆向遍历。 
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] strs = in.nextLine().split(",");
        int total = Integer.parseInt(strs[0]);
        int count = Integer.parseInt(strs[1]);
        String[] s1 = strs[2].split(" ");
        String[] s2 = strs[3].split(" ");
        int[] weight = new int[count];
        int[] values = new int[count];
        for (int i = 0; i < count; i++) {
            weight[i] = Integer.parseInt(s1[i]);
            values[i] = Integer.parseInt(s2[i]);
        }


        int[] dp = new int[total + 1];
        for (int i = 1; i <= count; i++) {
            for (int j = total; j >= weight[i - 1]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + values[i - 1]);
            }
        }

        System.out.println(dp[total]);
    }
    

}


发表于 2022-09-10 21:34:06 回复(0)
Java
pein531头像 pein531

记忆化搜索

通过暴力递归改出一版记忆化搜索
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));
        String[] params = br.readLine().split(",");
        int capacity = Integer.parseInt(params[0]);
        int types = Integer.parseInt(params[1]);
        String[] strs = params[2].split(" ");
        int[] limits = new int[types];
        for(int i = 0; i < types; i++){
            limits[i] = Integer.parseInt(strs[i]);
        }
        strs = params[3].split(" ");
        int[] values = new int[types];
        for(int i = 0; i < types; i++){
            values[i] = Integer.parseInt(strs[i]);
        }
        int[][] dp = new int[types][capacity + 1];
        System.out.println(dfs(0, limits, values, capacity, dp));
    }
    
    private static int dfs(int index, int[] limits, int[] values, int rest, int[][] dp) {
        if(index == values.length || rest <= 0){
            return 0;      // 到头了或当前资产拿不了了
        }
        if(dp[index][rest] > 0){
            return dp[index][rest];
        }
        // 不选当前的资产
        int p1 = dfs(index + 1, limits, values, rest, dp);
        // 选当前的资产
        int p2 = 0;
        if(rest >= limits[index])
            p2 = values[index] + dfs(index + 1, limits, values, rest - limits[index], dp);
        dp[index][rest] = Math.max(p1, p2);
        return dp[index][rest];
    }
}

动态规划

通过记忆化搜索的递归逻辑，可以改出动态规划，并注意到可以进行空间压缩，将二维表压缩为一维表 
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));
        String[] params = br.readLine().split(",");
        int capacity = Integer.parseInt(params[0]);
        int types = Integer.parseInt(params[1]);
        String[] strs = params[2].split(" ");
        int[] limits = new int[types];
        for(int i = 0; i < types; i++){
            limits[i] = Integer.parseInt(strs[i]);
        }
        strs = params[3].split(" ");
        int[] values = new int[types];
        for(int i = 0; i < types; i++){
            values[i] = Integer.parseInt(strs[i]);
        }
        int[] dp = new int[capacity + 1];
        for(int index = 0; index < types; index++){
            for(int rest = capacity; rest >= limits[index]; rest--){
                dp[rest] = Math.max(dp[rest], values[index] + dp[rest - limits[index]]);
            }
        }
        System.out.println(dp[capacity]);
    }
}

发表于 2022-01-12 22:54:48 回复(0)
Java
何止hz头像 何止hz
0-1背包问题动态规划解法，时空最优解的写法： 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] in = sc.nextLine().replaceAll(","," ").split(" ");
        int M = Integer.parseInt(in[0]);//载重
        int N = Integer.parseInt(in[1]);//种类
        int[] m= new int[N], v = new int[N];
        for (int i = 0; i < N; i++){
            m[i] = Integer.parseInt(in[i + 2]);
            v[i] = Integer.parseInt(in[i + 2 + N]);
        }
        int[] dp = new int[M + 1];
        for (int i = 0; i < N; i++){
            for (int j = M; j >= m[i]; j--){
                 dp[j] = Math.max(dp[j], dp[j - m[i]] + v[i]);
            }
        }
        System.out.println(dp[M]);
    }
}


发表于 2020-08-03 20:50:46 回复(0)
提交观点

问题信息

贪心 动态规划 安卓工程师 小米集团 2019
来自：小米2019秋招安卓开...
上传者：小小
难度：
4条回答 5428浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号