首页 > 试题广场 >

资产包打包

[编程题]资产包打包
  • 热度指数:3379 时间限制: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

0,1背包为题动态规划的详细解析原博客地址(https://blog.csdn.net/mu399/article/details/7722810)
有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?
图片说明
首先要明确这张表是至底向上,从左到右生成的。

为了叙述方便,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。

对于d2单元格,表示只有物品e,d时,承重为2的背包,所能装入的最大价值,仍然是0,因为物品e,d都不是这个背包能装的。

同理,c2=0,b2=3,a2=6。

对于承重为8的背包,a8=15,是怎么得出的呢?

根据01背包的状态转换方程,需要考察两个值,

一个是f[i-1,j],对于这个例子来说就是b8的值9,另一个是f[i-1,j-Wi]+Pi;

在这里,

f[i-1,j]表示我有一个承重为8的背包,当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值

f[i-1,j-Wi]表示我有一个承重为6的背包(等于当前背包承重减去物品a的重量),当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值

f[i-1,j-Wi]就是指单元格b6,值为9,Pi指的是a物品的价值,即6

由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9,所以物品a应该放入承重为8的背包

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = bf.readLine().split(",");
        int m = Integer.parseInt(strs[0]);//可容纳的资产 条
        int n = Integer.parseInt(strs[1]);//资产种类
        String[] sp1 = strs[2].split(" ");
        String[] sp2 = strs[3].split(" ");
        int[] kinds = new int[n];
        int[] prices = new int[n];
        for (int i = 0; i < sp1.length; i++) {
            kinds[i] = Integer.parseInt(sp1[i]);
            prices[i] = Integer.parseInt(sp2[i]);
        }
        //动态规划
        int[][] dp = new int[n + 1][m + 1];//dp[i][j],资产种类为i,背包重量为j
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //放入第i个种类的物品,该背包的剩余重量比i类物品的重量大或者相等
                //dp[i - 1][j] 为背包重量为j,不放入第i个物品的最大价值,
                // 和放入第i个物品时候的价值+前面i-1类中背包容量为j-
                /**
                 * dp[i - 1][j] 为背包重量为j,不放入第i个物品的最大价值
                 * dp[i - 1][j - kinds[i - 1]] + prices[i - 1] 为放入第i个物品+前i-1个物品中背包容量为j-i物品的重量的最大值
                 */
                if (j - kinds[i - 1] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - kinds[i - 1]] + prices[i - 1]);
                }else {//该类物品的重量大于背包的剩余重量了,装不下
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}
发表于 2019-07-28 13:29:04 回复(1)
/*
0-1背包问题,考虑动态规划,
设dp[n][m]为用前n件物品占用m空间,可以获得的最大价值。
其最大价值等于1、2最大值:1、不选最后一件物品所获价值,2、选择最后一件物品所获价值
dp[n][m] = max(dp[n-1][j],dp[n-1][j-t]+v) ,t为n物品占用空间,v为n物品价值。
*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
//    freopen("input.txt", "r", stdin);
    int m, n, i, j;
    char c;
    cin >> m >> c >> n >> c;
    int t[n + 1], v[n + 1];
    for(i = 1; i <= n; i++) cin >> t[i];
    cin >> c;
    for(i = 1; i <= n; i++) cin >> v[i];

    int dp[n + 1][m + 1];
    memset(dp, 0, sizeof(dp));
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if(t[i] <= j) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - t[i]] + v[i]);
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

发表于 2019-07-13 14:42:34 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    cin>>m;getchar();cin>>n;getchar();
    int zl[n+1],vl[n+1];
    for(int i=1;i<=n;i++)    cin>>zl[i];
    getchar();
    for(int i=1;i<=n;i++)    cin>>vl[i];
    int f[n+1][m+1];
    memset(f, 0, sizeof(f));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<zl[i];j++)
        {
            f[i][j]=f[i-1][j];
        }
        for(int j=zl[i];j<=m;j++)
        {
            f[i][j]=max(f[i-1][j],f[i-1][j-zl[i]]+vl[i]);
        }
    }
    cout<<f[n][m]<<endl;
}


谁笔试真的碰到这种真题,那就太幸福了,最基础的01背包连变形都没有。
发表于 2022-04-05 12:19:50 回复(0)

记忆化搜索

通过暴力递归改出一版记忆化搜索
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)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int m,n;
    char c;
    cin>>m>>c>>n>>c;
    int w[n+1], v[n+1];
    for(int i=1;i<=n;i++)
        cin>>v[i];
    cin>>c;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            dp[i][j] = dp[i-1][j];
            if(j>=v[i])
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]]+w[i]);
        }
    cout<<dp[n][m]<<endl;
    return 0;
}

发表于 2019-12-17 08:54:06 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int m,n;
    scanf("%d,%d,",&m,&n);
    vector<int> num(n,0),value(n,0);
    vector<vector<int>> dp(n,vector<int>(m+1,0));
    for(int i=0;i<n;i++)
        cin>>num[i];
    cin.ignore();
    for(int i=0;i<n;i++)
        cin>>value[i];
    for(int j=0;j<=m;j++)
        if(j>=num[0])
            dp[0][j]=value[0];
    for(int i=1;i<n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(j>=num[i])
                dp[i][j]=max(dp[i][j],dp[i-1][j-num[i]]+value[i]);
        }
    }
    cout<<dp[n-1][m];
    return 0;
}

发表于 2019-10-10 15:42:32 回复(0)

01背包 处理好边界就行了

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

int package01(const int & total,vector<int>&weight,vector<int>&value) {

    vector<vector<int>>dp(weight.size()+1,vector<int>(total+1,0));
    for (int i = 1;i < weight.size();++i) {
        for (int j = 1;j <= total ;++j) {

            if (weight[i] <=j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[weight.size()-1][total];
}
int main() {
    int total, number;
    char c;
    cin >> total >>c >> number>>c;


    vector<int>weight(number + 1, 0),values(number+1,0);
    for (unsigned int i = 0;i < number;++i) {
        cin >> weight[i + 1];

    }

    cin >> c;
    for (unsigned int i = 0;i < number;++i) {
        cin >> values[i + 1];

    }

    cout << package01(total,weight,values);
    system("pause");
    return 0;
}

发表于 2019-07-22 10:45:26 回复(0)
经典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)
#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <stack>
#include <map>
#include <list>
#include <ctime>
#include <queue>
#include <unordered_map>
#include <unordered_set>

class Solution {
public:
    //递归+剪枝
    int dfs(int total, size_t index, vector<int>& cost, vector<int>& values, vector<vector<int>>& record) {
        if (total < 0) {
            return -1;
        }
        if (index == cost.size()) {
            return 0;
        }
        if (record[total][index] != -1) {
            return record[total][index];
        }
        int unuse = dfs(total, index + 1, cost, values, record);
        int use = dfs(total - cost[index], index + 1, cost, values, record);
        if (use != -1) {
            use += values[index];
        }
        record[total][index] = max(use, unuse);
        return record[total][index];
    }
    
    int getMaxMoney(int total, vector<int>& cost, vector<int>& values) {
        vector<vector<int>> record(total + 1, vector<int>(cost.size(), -1));
        return dfs(total, 0, cost, values, record);
    }
    
    //动态规划
    int getMaxMoneyDp(int total, vector<int>& costs, vector<int>& values) {
        int n = costs.size();
        vector<vector<int>> dp(n + 1, vector<int>(total + 1, 0));
        for (int index = n - 1; index >= 0; index--) {
            for (int rest = 0; rest <= total; rest++) {
                int unuse = dp[index + 1][rest];
                int use = rest - costs[index] < 0 ? -1 : dp[index + 1][rest - costs[index]];
                if (use != -1) {
                    use += values[index];
                }
                dp[index][rest] = max(use, unuse);
            }
        }
        return dp[0][total];
    }
};

int main() {
    char temp;
    int total;
    int nums;
    cin >> total >> temp >> nums >> temp;
    vector<int> cost(nums);
    for (int i = 0; i < nums; i++) {
        cin >> cost[i];
    }
    cin >> temp;
    vector<int> values(nums);
    for (int i = 0; i < nums; i++) {
        cin >> values[i];
    }
    cout << Solution().getMaxMoneyDp(total, cost, values) << endl;
    return 0;
}

发表于 2022-07-31 14:33:32 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		while(in.hasNext()) {
			String[] s=in.nextLine().split(",");
			int capacity=Integer.valueOf(s[0]);
			int num=Integer.valueOf(s[1]);
			List<int[]> items=new ArrayList<>();
			String[] w = s[2].split(" ");//重量
			String[] v = s[3].split(" ");//价值
			for(int i=0;i<w.length;i++) {
				int[] item=new int[2];
				item[0]=Integer.valueOf(w[i]);
				item[1]=Integer.valueOf(v[i]);
				items.add(item);
			}
			
			int res = maxValueByXiaomi(capacity, items);
			System.out.println(res);
		}
	}
	//小米资产打包
	//总量m=12,种类n=3,重量w分别为4,5,7,价值v分别为500,600,800
	public static int maxValueByXiaomi(int capacity,List<int[]> items) {
		int n=items.size();
		int[][] dp=new int[n+1][capacity+1];//初始化0行0列方便dp
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=capacity;j++) {
				dp[i][j]=(items.get(i-1)[0]>j)?
						dp[i-1][j]:Math.max(dp[i-1][j], dp[i-1][j-items.get(i-1)[0]]+items.get(i-1)[1]);
			}
		}
		return dp[n][capacity];
	}
}

发表于 2020-08-06 12:23:00 回复(0)
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)
读题比做题花时间多的,搞得花里胡哨的。直接01背包不就好了。
01背包,滚动数组优化空间。
target,sort,nums,value = input().split(',')
target,sort = int(target.strip()),int(sort.strip())
nums,value = list(map(int,nums.strip().split())),list(map(int,value.strip().split()))
value,nums = [0]+value,[0]+nums
dpc = [0]*(target+1)

for i in range(len(value)):
    for j in range(target,-1,-1):
        if j>=nums[i]:
            dpc[j] = max(dpc[j],dpc[j-nums[i]]+value[i])

print(dpc[-1])



编辑于 2020-04-25 01:07:32 回复(0)
#include <iostream>
(720)#include <vector>
#include <cmath>
using namespace std;
int main(){
    int n,m;
    char c;
    cin>>n>>c>>m>>c;
    int *space=new int[m+1],*value=new int[m+1];
    for (int i=1;i<=m;i++) cin>>space[i];
    cin>>c;
    for (int i=1;i<=m;i++) cin>>value[i];
    vector<vector<int>> dp(m+1,vector<int>(n+1));
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            dp[i][j]=max(dp[i-1][j],j>=space[i]?dp[i-1][j-space[i]]+value[i]:0);
    cout<<dp[m][n];
}

// code2:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main(){
    int n,m;
    char c;
    cin>>n>>c>>m>>c;
    int *space=new int[m],*value=new int[m];
    for (int i=0;i<m;i++) cin>>space[i];
    cin>>c;
    for (int i=0;i<m;i++) cin>>value[i];
    int *ans=new int[n+1];
    for (int i=0;i<m;i++)
        for (int j=n;j>=space[i];j--){
            ans[j]=max(ans[j],ans[j-space[i]]+value[i]);
        }
   cout<<ans[n];
}

编辑于 2020-04-20 20:42:19 回复(0)
import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] strs = line.split(",");
        int c = Integer.parseInt(strs[0]);
        int n = Integer.parseInt(strs[1]);
        String[] wStr = strs[2].split(" ");
        String[] vStr = strs[3].split(" ");
        int[] weights = new int[n];
        int[] values = new int[n];
        for(int i=0;i<n;i++){
            weights[i] = Integer.parseInt(wStr[i]);
            values[i] = Integer.parseInt(vStr[i]);
        }
        int[][] dp = new int[n+1][c+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=c;j++){
                if(j>=weights[i-1]){
                    dp[i][j] = Math.max(dp[i-1][j-weights[i-1]]+values[i-1],dp[i-1][j]);
                }else
                    dp[i][j] = dp[i-1][j];
            }
        }
        System.out.println(dp[n][c]);
        
    }
}

发表于 2020-02-10 20:54:37 回复(0)
弱智版😁
#include<sstream>
#include<iostream>
#include<cstring>
using namespace std;

int f(string s){
    int ans=0;
    for(int i=0;i<s.size();i++) ans=ans*10+s[i]-'0';
    return ans;
}

int main(){
    string s;
    int ww,nn;
    int w[1001];
    int v[1001];
    int dp[1000005];
    while(getline(cin,s)){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<s.size();i++){
            if(s[i]==',') s[i]=' ';
        }
        istringstream sin(s);
        string ss;
        int l=0;
        while(sin>>ss){
            if(l==0) ww=f(ss);
            if(l==1) nn=f(ss);
            if(l>1&&l<2+nn) w[l-2]=f(ss);
            if(l>=2+nn&&l<2+2*nn) v[l-2-nn]=f(ss);
            l++;
        }
        for(int i=0;i<nn;i++){
            for(int j=ww;j>=w[i];j--){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        cout<<dp[ww]<<endl;
    }
    return 0;
}

发表于 2019-09-01 13:36:13 回复(0)
# 动态规划
space, cls, sizes, values = input().split(",")
space = int(space)
cls = int(cls)
sizes = list(map(int, sizes.strip().split(" ")))
values = list(map(int, values.strip().split(" ")))
dp = [[0]*(space+1) for i in range(cls+1)]
for i in range(1, cls+1):
    size = sizes[i-1]
    value = values[i-1]
    for j in range(0, space+1):
        if j >= size:
            dp[i][j] = max(dp[i-1][j-size]+value, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][-1])

编辑于 2019-08-20 19:29:42 回复(0)
博客有本题介绍,并给出牛客网类似题目的思路,欢迎指正。
https://blog.csdn.net/weixin_42564710/article/details/97111434
total,label,number,value = input().split(',')
number = list(map(int,number.split()))
value = list(map(int,value.split()))
#print(value)
dp = [0]*(int(total)+1)
for i in range(int(label)): # i是种类数
    for j in range(len(dp)-1,number[i]-1,-1): #j是number[i]到最大总量之间的数值
        dp[j] = max(dp[j],dp[j-number[i]]+value[i])
print(dp[-1])

发表于 2019-07-24 11:30:02 回复(0)