首页 > 试题广场 >

乔乔的包

[编程题]乔乔的包

热度指数：1547 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

玥玥带乔乔一起逃亡，现在有许多的东西要放到乔乔的包里面，但是包的大小有限，所以我们只能够在里面放入非常重要的物品。现在给出该种物品的数量、体积、价值的数值，希望你能够算出怎样能使背包的价值最大的组合方式，并且输出这个数值，乔乔会非常感谢你。

输入描述:

第1行有2个整数，物品种数n和背包装载体积v；

第2行到i+1行每行3个整数，为第i种物品的数量m、体积w、价值s。

输出描述:

仅包含一个整数，即为能拿到的最大的物品价值总和。

示例1

输入

2 10
3 4 3
2 2 5

输出

说明

选第一种一个，第二种两个，结果为3x1+5x2=13。

备注:

1≤v≤500

1≤n≤2000

1≤m≤10

1≤w≤20

1≤s≤100

算法知识视频讲解

向宇回桌

import java.util.*;

public class Main {
    private static final int N_MAX = 2005;
    private static final int V_MAX = 505;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), v = sc.nextInt();
        int[] vs = new int[N_MAX], ws = new int[N_MAX], nums = new int[N_MAX];
        for (int i=1; i<=n; i++) {
            nums[i] = sc.nextInt(); vs[i] = sc.nextInt(); ws[i] = sc.nextInt();
        }
        int[] dp = new int[V_MAX];
        for (int i=1; i<=n; i++) {
            for (int j=v; j>=vs[i]; j--) {
                for (int k=1; k <= nums[i] && k*vs[i]<=j; k++) {
                    dp[j] = Math.max(dp[j], dp[j-k*vs[i]] + k* ws[i]);
                }
            }
        }
        System.out.println(dp[v]);
    }
}

发表于 2019-02-28 16:05:30 回复(0)

我是如此相信

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    private static class Good {
        int w;
        int s;
        public Good(int w, int s) {
            super();
            this.w = w;
            this.s = s;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();
        List<Good> goods = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int m = scanner.nextInt(), w = scanner.nextInt(), s = scanner.nextInt();
            for (int j = 0; j < m; j++) {
                goods.add(new Good(w, s));
            }
        }
        System.out.println(solve(goods, v));
    }
    private static int solve(List<Good> goods, int v) {
        int[] dp = new int[v + 1];
        for (int i = 0; i < goods.size(); i++) {
            Good good = goods.get(i);
            for (int j = v; j >= 1; j--) {
                if (j >= good.w) {
                    dp[j] = Math.max(dp[j], dp[j - good.w] + good.s);
                }
            }
        }
        return dp[v];
    }
}

发表于 2019-05-31 15:00:43 回复(1)

牛客329247131号

逆序更新dp以节约空间

递推公式：dp[j] = max(dp[j], dp[j-ws[i]*k]+ss[i]*k)

此时dp[j-ws[i]*k]是到i-1个物品的最大价值。

n, v = map(int, input().strip().split())
ms = []
ws = []
ss = []
for _ in range(n):
    m, w, s = map(int, input().strip().split())
    ms.append(m)
    ws.append(w)
    ss.append(s)
dp = [0]*(v+1)
for i in range(n):
    for j in range(v, -1, -1):  # 节约空间逆序更新dp
        for k in range(ms[i]+1):
            if j-ws[i]*k >= 0:
                dp[j] = max(dp[j], dp[j-ws[i]*k]+ss[i]*k)
print(dp[-1])

发表于 2021-04-07 18:05:03 回复(0)

Python

白色纯度

python的答案好多都是贪心，贪心真的是最优解吗？我还是选择动态规划吧！

发表于 2019-09-12 09:55:36 回复(0)

Dejavu_Get

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


int main()
{
    int n=0,v=0;
    cin>>n;cin>>v;
    
    vector<int> m(n);
    vector<int> w(n);
    vector<int> s(n);
    vector<int> dp(v+1);
    for(int i=0;i<n;i++)
        cin>>m[i]>>w[i]>>s[i];

 for (int i=0; i<n; i++) {
            for (int j=v; j>=w[i]; j--) {
                for (int k=0; k <=m[i] && k*w[i]<=j; k++) {
                    dp[j] = max(dp[j], dp[j-k*w[i]] + k* s[i]);
                }
            }
        }
    
    cout<<dp[v];
    
    
    
    
}

发表于 2019-08-27 18:27:10 回复(0)

PopcornZQ

多重背包问题，为了空间复杂度，可以采用降维。为了时间复杂度，采用二进制优化。当然你也可以用单调队列。这里我采用了降维加二进制优化。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int V;
void zeroonepack(vector<int> &result, vector<int> v, vector<int> value, int i)
{
	for (int j = V; j >= v[i]; --j)
	{
		j < v[i] ? result[j] = result[j] : result[j] = max(result[j], result[j - v[i]] + value[i]);//放不下第i个物体
	}
	return;
}
int main()
{
	int n, temp1, temp2, temp3, k = 1;//背包体积V，n组数
	cin >> n >> V;
	vector<int> num(n + 1, 0), v(1, 0), value(1, 0), result(V + 1, 0);/*v是物体体积，value是物体价值。result[i]表示前i个物品，
																	  放到v中最大价值,需要初始化为0。如果需要刚好放满背包，除了第0个元素，其他要初始化为负无穷。v和value只申请一个是因为第0个要为0*/
	for (int i = 1; i <= n; ++i)
	{
		cin >> temp1 >> temp2 >> temp3;
		num[i] = temp1;
		while (k < num[i])//未进入循环的时候，即等于原num[i]-2^k+1
		{
			v.push_back(k*temp2);
			value.push_back(k*temp3);
			num[i] -= k;
			k = k * 2;
		}
		v.push_back(num[i] * temp2);
		value.push_back(num[i] * temp3);//补差值
		k = 1;
	}
	for (int i = 1; i <= v.size(); ++i)//二进制优化01背包后，有v.size()个物品
		zeroonepack(result, v, value, i);
	cout << result[V] << endl;
	return 0;
}

发表于 2019-08-07 10:46:30 回复(0)

vaee

#include<bits/stdc++.h>

using namespace std;

//标准的多重背包，百度背包问题的百度百科就知道了

int main()
{
int N,W; //分别代表物品种数和体积
cin>>N>>W;
int m[2002],w[2002],s[2002];//分别代表某种物品的数量，体积，价值
for(int i=0;i<N;i++)
cin>>m[i]>>w[i]>>s[i];
int dp[2002]={0};
for(int i=0;i<N;i++)
for(int j=W;j>=w[i];j--)
for(int k=1;k<=m[i]&&k*w[i]<=j;k++)
dp[j] = max(dp[j],dp[j-k*w[i]]+s[i]*k);
cout<<dp[W];
}

发表于 2019-03-01 10:23:35 回复(0)

提交观点

问题信息

动态规划

上传者：小小

难度：

7条回答 24收藏 3137浏览

通过挑战的用户

查看代码

前端学习中

2022-08-27 18:55:13
MC枫少

2022-06-24 14:29:58
祈求顺利毕业

2022-06-15 20:44:23
大佬带飞

2022-05-25 22:39:55
up淋雨

2022-05-18 19:55:29

乔乔的包

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题