首页 > 试题广场 >

双袋购物

[编程题]双袋购物

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

一条马路上有 n 个点，从左到右从 1 到 n 编号。小明一开始在马路的最左边，一直往右走，一直走到马路的最右边，一直往右走，一直走到马路的最右边，中途不允许回头，只能往右走。

每个点上都有一个物品，第 i 个点的物品体积为 v_i，价值为 w_i，(注意：先输入体积再输入价值)小明有两个袋子，一号袋子和二号袋子，一号袋子体积为 A ，二号袋子体积为 B 。

最开始小明使用一号袋子，经过一个点的时候，他可以选择把点上的物品放入袋子中，但是袋中物品的总体积不能超过袋子的体积，也可以选择不拿这个物品。

在整个过程中的任意一个时刻，小明可以选择把一号袋子收起来，接下来使用二号袋子，一旦小明收起了一号袋子，之后他再也不能使用一号袋子，接下来的物品只能决策是否放入二号袋子中，且袋中的物品的总体积不能超过袋子容量。特别的，小明可以在最开始（遇到 1 号点之前）就换袋子，这样他全程都使用二号袋子；他也可以一直使用一号袋子，到最后也不收。

小明最后获得的价值为两袋子中物品价值和，问在最优策略下的最大价值。

数据范围： $1 \le n , A , B , v_i , w_i \le 1000 \$

输入描述:

输入第一行三个数 n , A , B。
接下里有 n 行，每行两个数 v_i , w_i 依次表示每个物品的体积和价值。

输出描述:

输出一个数，最大价值

示例1

输入

输出

说明

用一号袋子装1号和3号物品，之后收起一号袋子，用二号袋子装4号物品。

算法知识视频讲解

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, A, B, Max=0;
    scanf("%d%d%d", &n, &A, &B);
    int v[n], w[n], a[n]={0}, b[n]={0}, dp1[A+1]={0}, dp2[B+1]={0};
    for(int i=0;i<n;i++)
        scanf("%d%d", &w[i], &v[i]);
    for(int i=0;i<n;i++){
        for(int j=A;j>=w[i];j--)
            dp1[j] = max(dp1[j], dp1[j-w[i]]+v[i]);
        a[i] = dp1[A];
    }
    for(int i=n-1;i>=0;i--){
        for(int j=B;j>=w[i];j--)
            dp2[j] = max(dp2[j], dp2[j-w[i]]+v[i]);
        b[i] = dp2[B];
    }
    for(int i=0;i<n-1;i++)
        Max = max(Max, a[i]+b[i+1]);
    printf("%d\n", Max);
    return 0;
}

发表于 2020-09-16 13:46:30 回复(0)

ChessC

一开始，0-1背包问题无疑，那么多了一种混合情况，可以使用A在任意点进行更换后使用B，那么直接对于位置进行划分然后dp
//单列dp问题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution{
public:
    int MaxV(vector<int>&v,vector<int>&w,int limit,int begin,int end){ //limit为背包限定总重
        int n=v.size();
        vector<int> dp(limit+1,0); //0-1背包，重量逆序
        for(int i=begin;i<end;++i)
            for(int j=limit;j>=w[i];--j)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        return dp[limit];
    }
};
int main(){
    int n,A,B,idx=0;
    cin>>n>>A>>B;
    vector<int> value(n);
    vector<int> weight(n);
    while(n--){
        cin>>weight[idx]>>value[idx];
        idx++;
    }
    Solution sol;
    int All_A=sol.MaxV(value,weight,A,0,n);
    int All_B=sol.MaxV(value,weight,B,0,n);
    int combination=0;
    n=(int)value.size();
    for(int i=0;i<n;++i)
        combination=max(combination,sol.MaxV(value,weight,A,0,i)+sol.MaxV(value,weight,B,i,n));
    cout<<max(max(All_A,All_B),combination);
    return 0;
}
但只能AC80%，复杂度过大，原因是我想用一个通式计算背包最大结果，因此在混合的时候，我不断进行两个数组的划分然后再进行递归调用，此处开销过大。
之后看到上面这位写的，确实，只要进行A,B时候两次计算即可，多用两个数组来保存位置信息。之后混合的时候无需再及逆行递归了。
//单列dp问题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n,A,B,idx=0;
    cin>>n>>A>>B;
    vector<int> value(n);
    vector<int> weight(n);
    while(n--){
        cin>>weight[idx]>>value[idx];
        idx++;
    }
    n=(int)value.size();
    vector<int> All_A(n,0);
    vector<int> All_B(n,0);
    vector<int> dpA(A+1,0);
    vector<int> dpB(B+1,0);
    for(int i=0;i<n;++i){
        for(int j=A;j>=weight[i];--j)
            dpA[j]=max(dpA[j],dpA[j-weight[i]]+value[i]);
        All_A[i]=dpA[A];
    }
    for(int i=n-1;i>=0;--i){
        for(int j=B;j>=weight[i];--j)
            dpB[j]=max(dpB[j],dpB[j-weight[i]]+value[i]);
        All_B[i]=dpB[B];
    }
    int combination=0;
    for(int i=0;i<n-1;++i)
        combination=max(combination,All_A[i]+All_B[i+1]);
    cout<<combination;
    return 0;
}

发表于 2019-02-25 10:57:56 回复(1)

Java

刘禅挥泪斩孔明

public class Main {
  public static void main(String[] args) {
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int n=sc.nextInt(), A=sc.nextInt(), B=sc.nextInt(), i, j, maxVal=0;
    int bagA[]=new int[A+5], bagB[]=new int[B+5], ansA[]=new int [n+5],
        ansB[]=new int[n+5], volume[]=new int[n+5], value[]=new int[n+5];
    for (i = 1; i <= n; ++i) {
      volume[i] = sc.nextInt();
      value[i] = sc.nextInt();
      for (j = A; j >= volume[i]; --j)//对袋子1进行动态规划
        bagA[j] = Math.max(bagA[j], bagA[j-volume[i]] + value[i]);
      ansA[i] = bagA[A];//ansA[i]:一直使用袋子1到第i个节点时的最大总价值
    }
    for (i = n; i > 0; --i) {//对袋子2进行动态规划，反向进行
      for (j = B; j >= volume[i]; --j)
        bagB[j] = Math.max(bagB[j], bagB[j-volume[i]] + value[i]);
      ansB[i] = bagB[B];//ansB[i]:使用袋子2从第i个节点到最后的最大总价值
    }
    for (i = 0; i <= n; ++i)//求在各个节点换袋子的决策能得到的最大总价值
      maxVal = Math.max(maxVal, ansA[i] + ansB[i+1]);
    System.out.println(maxVal);//时间复杂度:O(n*(A+B))
  }
}

编辑于 2018-07-04 16:23:05 回复(0)

Python3

喜欢走神的托尼all-in实习

#思路是分别使用两个袋子独立地做一遍，这个时候变成简单的01问题，需要注意的是袋子2从后往前遍历物品。
#做的时候用一个ans数组记录每个位置i时候，两个袋子分别的最大价值，
#最后遍历i，找到一个节点i使得ansA[i]+ansB[i+1]最大，i节点换袋子

import sys

n , A , B = list(map(int,input().split()))

#print(n,A,B)

values = []

weights = []

for line in sys.stdin:

wi,vi = list(map(int,line.split()))

values.append(vi)

weights.append(wi)

dpA = [0]*(A+1)

ansA = [0]*(n+1)

dpB = [0]*(B+1)

ansB = [0]*(n+1)

for i in range(n):

for j in range(A,weights[i]-1,-1):

dpA[j] = max(dpA[j],dpA[j-weights[i]]+values[i])

ansA[i] = dpA[A]

for i in range(n-1,-1,-1):

for j in range(B,weights[i]-1,-1):

dpB[j] = max(dpB[j],dpB[j-weights[i]]+values[i])

ansB[i] = dpB[B]

res = 0

for i in range(n):

res = max(res,ansA[i]+ansB[i+1])

# print(ansA)

# print(ansB)

print(res)

编辑于 2024-04-14 15:42:47 回复(0)

想回家的海螺在拧螺丝

#include <bits/stdc++.h>
#include <vector>
using namespace std;

int main() {
    int n, A, B;
    cin >> n >> A >> B;

    vector<vector<int>> nums(n); //体积,价值

    int v;
    int w;
    for (int i = 0; i < n; i++) {
        cin >> v >> w;
        nums[i] = {v, w};
    }

    vector<int> dpA(A + 1), ansA(n+1);
    vector<int> dpB(B + 1), ansB(n+1);

    for (int i = 0; i < nums.size(); i++) {
        for (int j = A; j >= nums[i][0]; j--) {
            dpA[j] = max(dpA[j], dpA[j - nums[i][0]] + nums[i][1]);
        }
        ansA[i] = dpA[A];
    }

    for (int i = nums.size()-1; i >= 0; i--) {
        for (int j = B; j >= nums[i][0]; j--) {
            dpB[j] = max(dpB[j], dpB[j - nums[i][0]] + nums[i][1]);
        }
        ansB[i] = dpB[B];
    }

    int ans = ansB[0];
    for(int i = 0; i < n; i++) {
        ans = max(ans, ansA[i]+ansB[i+1]);
    }

    cout<<ans;

    return 0;
}

发表于 2023-05-06 12:42:30 回复(0)

嘀嘀复嘀嘀

#include<bits/stdc++.h>
#define MAX_LEVEL 16
using namespace std;
struct node {
	int v, w;
	node() {}
};
vector<int> helper(vector<node>&v, int l, int r, int V)
{
	int n = v.size();
	vector<int>ans(n +1, 0);
	vector<int>value(V+1,-1);
	value[0] = 0;
	for (int i = l; i <= r; i++)
	{
		for (int j = V; j >= v[i].v; j--)
		{
			
			if (value[j - v[i].v] != -1)
			{
				value[j] = max(value[j - v[i].v] + v[i].w, value[j]);
			}
			ans[i] = max(ans[i], value[j]);
			if (i > 0)
				ans[i] = max(ans[i], ans[i - 1]);
		}
	}
	return ans;
}
int main()
{
	int n, A, B;
	cin >> n >> A >> B;
	vector<node>v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i].v >> v[i].w;
	}
	vector<int>AA = helper(v, 0, n - 1, A);
	reverse(v.begin(), v.end());
	vector<int>BB = helper(v, 0, n - 1, B);
	int ans = 0;
	for (int i =1; i < n - 1; i++)
	{
		ans = max(ans, AA[i] + BB[n - i - 2]);
	}
	ans = max(AA[n - 1], ans);
	ans = max(ans, BB[n - 1]);
	cout << ans << endl;
}

发表于 2020-06-15 08:24:10 回复(0)

牛牛56

#include<iostream>
#include<math.h>
using namespace std;

int v[1005],w[1005];
int main()
{
int n,a,b;
    int a_z[1005]={0},a_dpz[1005]={0},b_f[1005]={0},b_dpf[1005]={0};
cin>>n>>a>>b;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
    for(int i=1;i<=n;i++) // 袋子a是正向走
    {
        for(int j=a;j>=v[i];j--)//反向遍历，优化空间
            a_dpz[j]=max(a_dpz[j],a_dpz[j-v[i]]+w[i]);
        a_z[i] =a_dpz[a];
    }
    for(int i=n;i>0;i--) //袋子b是反向走，因为b走的是a的剩余部分
    {
        for(int j=b;j>=v[i];j--)
            b_dpf[j] = max(b_dpf[j],b_dpf[j-v[i]]+w[i]);
        b_f[i]=b_dpf[b];
    }
    int max_res=0;
    for(int i=1;i<=n;i++)
    {
        max_re***ax(max_res,a_z[i]+b_f[i+1]);
    }
    cout<<max_re***r /> return 0;
}

发表于 2019-05-20 10:54:17 回复(0)

苏苏#学长

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strs = br.readLine().split(" ");
int num = Integer.parseInt(strs[0]);
int w1 = Integer.parseInt(strs[1]), w2 = Integer.parseInt(strs[2]);

int[] v = new int[num + 2], w = new int[num + 2];
for (int i = 1; i <= num; i++) {
strs = br.readLine().split(" ");
v[i] = Integer.parseInt(strs[0]);
w[i] = Integer.parseInt(strs[1]);
}
int[] v1=new int[w1+1],resA=new int[num+2];//+2 头尾各预留一个0,应对全是一号袋子或全是二号袋子

        for(int i=1;i<=num;i++) {
            for(int j=w1;j>=v[i];j--) {
                    v1[j]=Math.max(v1[j-v[i]]+w[i], v1[j]);
                }
            resA[i]=v1[w1];//一号袋子从第一个节点到第I个节点
        }
        int[] v2=new int[w2+1],resB=new int[num+2];//+2
        for(int i=num;i>0;i--){
            for(int j=w2;j>=v[i];j--) {
                    v2[j]=Math.max(v2[j-v[i]]+w[i], v2[j]);
                }
            resB[i]=v2[w2];//二号袋子从第I个节点到最后一个节点
        }
        int max=0;
        for(int i=0;i<=num;i++) {
            max=Math.max(resA[i]+resB[i+1], max);//一号袋子从第一个节点到第I个节点，叠加上二号袋子从第I+1个节点到最后一个节点
        }
        System.out.println(max);

}
}

发表于 2019-03-19 19:26:35 回复(0)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        int a = Integer.parseInt(strs[1]), b = Integer.parseInt(strs[2]);

        int[] v = new int[n + 2], w = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            strs = br.readLine().split(" ");
            v[i] = Integer.parseInt(strs[0]);
            w[i] = Integer.parseInt(strs[1]);
        }

        int[] bagA = new int[a + 1], resA = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            for (int j = a; j >= v[i]; j--) {
                bagA[j] = Math.max(bagA[j], bagA[j - v[i]] + w[i]);
            }
            resA[i] = bagA[a];
        }

        int[] bagB = new int[b + 1], resB = new int[n + 2];
        for (int i = n; i > 0; i--) {
            for (int j = b; j >= v[i]; j--) {
                bagB[j] = Math.max(bagB[j], bagB[j - v[i]] + w[i]);
            }
            resB[i] = bagB[b];
        }

        int res = 0;
        for (int i = 0; i <= n; i++) {
            res = Math.max(res, resA[i] + resB[i + 1]);
        }
        System.out.println(res);
    }
}

发表于 2019-03-13 19:15:42 回复(0)