首页 > 试题广场 >

多重背包

[编程题]多重背包
  • 热度指数:2559 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
有一个体积为V的背包,有m种物品,每种物品有体积和价值,且数量一定。求背包能装下的最大价值。

输入描述:
第一行两个整数V和m。
接下来m行,每行3个整数,表示第i种物品的数量、体积和价值。
,个数、体积、价值不超过1000。


输出描述:
输出一个整数,表示背包能装下的最大价值。
示例1

输入

10 4
2 3 2
2 4 3
1 2 2
4 5 3

输出

8
参考了很多大佬的Java和c++代码,前端狗的JavaScript版本来了!
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    const arr1 = (await readline()).split(" ");
    const capacity = parseInt(arr1[0]);
    const n = parseInt(arr1[1]);
    const amounts = [];
    const weights = [];
    const values = [];
    for (let i = 0; i < n; i++) {
        let tokens = (await readline()).split(" ");
        amounts.push(parseInt(tokens[0]));
        weights.push(parseInt(tokens[1]));
        values.push(parseInt(tokens[2]));
    }
    const dp = new Array(capacity + 1).fill(0);
    for (let i = 0; i < n; i++) {
        if (weights[i] >= capacity) {
            zero_oneBP(1);
        }
        let k = 1;
        while (k <= amounts[i]) {
            zero_oneBP(k);
            amounts[i] -= k;
            k = k * 2;
        }

        if (amounts[i] > 0) zero_oneBP(amounts[i]);

        function zero_oneBP(k) {
            for (
                let remain_v = capacity;
                remain_v >= k * weights[i];
                remain_v--
            ) {
                let temp = k * values[i] + dp[remain_v - k * weights[i]];
                dp[remain_v] = Math.max(temp, dp[remain_v]);
            }
        }
    }
    console.log(dp[capacity]);
})();


发表于 2023-03-19 22:41:12 回复(0)
import java.util.*;
public  class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int m = sc.nextInt();
        int []num = new int[m];
        int []vArr = new int[m];
        int []value = new int[m];
        for(int i=0;i<m;i++){
            num[i] = sc.nextInt();
            vArr[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        
        int [] dp = new int[v+1];
        for(int i=0;i<m;i++){
            if(num[i]*vArr[i]>=v){
                for(int j=vArr[i];j<=v;j++){
                    dp[j] = Math.max(dp[j],dp[j-vArr[i]]+value[i]);
                }
            }else{
                int k=1;
                int temp=num[i];
                while(k<temp){
                    int v_tmp =k*vArr[i];
                    for(int j=v; j>=v_tmp;j--){
                        dp[j] = Math.max(dp[j],dp[j-v_tmp]+k*value[i]);
                    }
                    temp -=k;
                    k*=2;
                }
                for(int j=v; j>=temp*vArr[i];j--){
                    dp[j] = Math.max(dp[j],dp[j-temp*vArr[i]]+temp*value[i]);
                }
            }
        }
        
       System.out.println(dp[v]);
    }
}
中间对数量进行了判断,当用不完的时候相当于完全背包,就用完全背包去解。毕竟完全背包这边不用拆分,时间上会短点。然后01背包用了二进制优化

发表于 2021-06-23 21:59:23 回复(0)
//多重背包拆成01背包,以及优化为1维
# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

struct Pair
{
    int v;
    int w;    
};

int main(void)
{
    int i;
    int j;
    int n;
    int V;
    cin >> V >> n;
    if (n == 0 || V == 0)
        return 0;
    int v;
    int w;
    int s;
    vector<struct Pair> good;
    
    struct Pair * temp;
    for (i = 1; i <= n; i++)
    {
        cin >> s >> v >> w;
        //需要把s[i]拆成 log(s[i]) + 1(如果剩余)  份
        for (j = 1; j <= s; s-= j, j *= 2) //二进制拆法 
        {
            temp = new Pair();
            temp->v = v * j;  //体积 
            temp->w = w * j;  //价值 
            good.push_back(*temp);
        
        if (s != 0)
        {
            temp = new Pair();
            temp->v = v * s;  //体积 
            temp->w = w * s;  //价值 
            good.push_back(*temp);            
        
    }
    //需要拆成一份一份,然后放到数组中,最后变成一个01背包问题,选和不选两种选择 
    n = good.size();
    vector<int> f(V + 1, 0);  //体积还是不变,只是物品的数量变多了 
    for (i = 1; i <= n; i++)  //需要优化为1维,否则内存会超
    {
        for (j = V; j >= good[i - 1].v; j--)
        {
            if (good[i - 1].v <= j)
                f[j] = max(f[j], f[j - good[i - 1].v] + good[i - 1].w);
        }
    }
    cout << f[V] << endl;
    
    return 0;
}
编辑于 2020-08-15 21:32:36 回复(0)
好奇怪,我的自测用例和在acwing的多重背包练习中能ac,提交之后无法通过。。。
w,n = map(int,input().split())
try:
    goods = []
    while n:
        n-=1
        goods.append(list(map(int,input().split())))
    n = len(goods)
    new_goods= []
    for i in range(n):
        for j in range(goods[i][0]):
            new_goods.append([goods[i][1],goods[i][2]])#体积,价值
    #goods.clear()
    n = len(new_goods) #重新定义总数量
    #01 背包
    dp = [0]*(w+1) #第i个物品总容量为j时最大价值
    for i in range(1,n+1):
        for j in range(w,new_goods[i-1][0]-1,-1):
            dp[j] = max(dp[j],dp[j-new_goods[i-1][0]]+new_goods[i-1][1])
    print(dp[-1])
except:
    pass


编辑于 2020-08-05 15:49:44 回复(0)
/*
第一行两个整数V和m。
接下来m行,每行3个整数,表示第i种物品的数量、体积和价值。
V≤104, m≤500V\leq10^4,\ m≤500V≤104, m≤500,个数、体积、价值不超过1000。
*/
#include<iostream>
(720)#include<vector>
using namespace std;

int main() {
  int V, M; //体积为V 有m种物品
  cin >> V >> M;
  vector<std::pair<int, int>> goods; //物品的体积 物品的价值
  for (int i = 0; i < M; ++i) {
    int num, v, value;
    cin >> num >> v >> value;
    int n = 1;         //物品分块的数量
    while (n <= num) { // n应当小于1
      goods.push_back({n * v, n * value});
      num -= n;
      n <<= 1;
    }
    if (num != 0)
      goods.push_back({num * v, num * value});
  }
  // dp[i][v]//选择第i次后 体积为v时的最大价值
  vector<int> dp(V + 1, 0);
  for (int i = 1; i <= goods.size(); ++i) {
    for (int j = V; j > 0; --j) {
      if (j >= goods[i - 1].first)
        dp[j] = max(dp[j], dp[j - goods[i - 1].first] + goods[i - 1].second);
    }
  }
  cout << dp.back() << endl;
  return 0;
}

发表于 2020-04-24 18:53:34 回复(0)
//ac多重背包转换01背包
//如何拆分?10个可以拆封成 1  2  4  还剩3个
//不管怎么样,拆分后可以还原(0-10)每一种情况
#include <iostream>
using namespace std;
struct E{
    int w;  //体积
    int v;  //重量
}lis[20005];
int dp[20005];
int Max(int a,int b){
    return a>b?a:b;
}
int main(){
    int n,m;
    int k,p,h;
    cin>>n>>m;
    int index = 0;             //拆分后物品总数
    for(int i=1;i<=m;i++){
        cin>>k>>p>>h;          //数量\体积\重量
        int c = 1;
        while(k-c>0){                //拆分
            k -= c;
            lis[++index].w = c*p;
            lis[index].v = c*h;
            c*= 2;
        }
        lis[++index].w = p*k;     //补充不足指数的差值
        lis[index].v = h*k;
    }
    for(int i=1;i<=index;i++){   //0-1背包
        for(int j=n;j>=lis[i].w;j--)
            dp[j]=Max(dp[j],dp[j-lis[i].w]+lis[i].v);
    }
    cout<<dp[n]<<endl;
    return 0;
}
发表于 2019-09-11 16:02:30 回复(0)
#include <bits/stdc++.h>

using namespace std;

struct item
{
    int w;
    int v;

} l[10000];
int dp[10001];

int main()
{
    int maxv, n;

    while (cin >> maxv >> n)
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            int v, w, k;
            cin >> k >> w >> v;
            int temp = 1;
            while (k - temp > 0)
            {
                k -= temp;
                l[++cnt].w = temp * w;
                l[cnt].v = temp * v;
                temp *= 2;
            }
            l[++cnt].w = w * k;
            l[cnt].v = v * k;
        }
        for (int i = 0; i <= maxv; i++)
        {
            dp[i] = 0;
        }
        for (int i = 1; i <= cnt; i++)
        {
            for (int j = maxv; j >= l[i].w; j--)
            {
                dp[j] = max(dp[j], dp[j - l[i].w] + l[i].v);
            }
        }
        cout << dp[maxv];
    }
    return 0;
}

发表于 2019-09-08 21:11:25 回复(0)
import java.util.Scanner;
public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
            int total = sc.nextInt();
            int n = sc.nextInt();
            int num[] = new int[n];
            int m[] = new int[n];
            int v[] = new int[n];
            for (int i = 0; i < n; i++) {
                num[i] = sc.nextInt();
                m[i] = sc.nextInt();
                v[i] = sc.nextInt();
             //   System.out.println('s');
            }
            long[] dp = new long[total + 1];
        //    for (int i = 1; i * c[i] < total && i <= b[i]; i++) {
          //      dp[0][i * c[i]] = i * d[i];
            //}
            for (int i = 0; i < n; i++) {
                int t=Math.min(total/m[i],num[i]);//取数量最大值
                for (int k = 1;t>0;k<<=1) {//数量二进制分组
                    if(k>t)k=t;
                    t-=k;
                    for (int j =total; j>=k*m[i]; j--) {                      
                      dp[j] = Math.max(dp[j - k*m[i]] + k*v[i], dp[j]);                      
                    }
                }
            }      
            System.out.println(dp[total]);   
}
}


发表于 2019-08-11 11:19:50 回复(0)
#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 >> V >> n;
    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-05 20:09:28 回复(0)
/**
* @author: karlmical
* @date: 20190805
*
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <sstream>
#include <string.h>
using namespace std;
const int MAXV = int(1e4) + 5;
const int MAXN = 1000 + 1;
int dp[MAXV];
int capacity[MAXN], vol[MAXN], value[MAXN];
void zeroone_knapsack(int limit, int i, int k)
{
const int w = k * vol[i];
for (int j = limit; j >= w; j--)
{
int nv = dp[j - w] + k * value[i];
if (nv > dp[j])
{
dp[j] = nv;
}
}
}
int multi_knapsack(int n, int limit)
{
//init
memset(dp, 0, sizeof(int) * (n + 1));
for (int i = 1; i <= n; i++)
{
if (vol[i] * capacity[i] >= limit)
{
for (int j = vol[i]; j <= limit; j++)
{
int nv = dp[j - vol[i]] + value[i];
if (nv > dp[j])
{
dp[j] = nv;
}
}
}
else
{
int k = 1, res = capacity[i];
while (k < res)
{
zeroone_knapsack(limit, i, k);
res -= k;
k <<= 1;
}
zeroone_knapsack(limit, i, res);
}
}
return dp[limit];
}
int main()
{
int v, m;
cin >> v >> m;
for (int i = 1; i <= m; i++)
{
cin >> capacity[i] >> vol[i] >> value[i];
}
cout << multi_knapsack(m, v);
return 0;
}

编辑于 2019-08-05 15:04:31 回复(1)
import java.util.Arrays;
import java.util.Scanner;
import java.util.ArrayList;
/**
 * @Classname BeiBao_01
 * @Description 有N中类型的商品,每一个有自己的体积w[i],价值v[i],容量是V,求最大的价值W
 * 注意:这是一个01背包问题,每一件商品只有1个,多重背包转换为01背包
 * @Date 19-6-9 下午7:34
 * @Created by mao<tianmao818@qq.com>
 */
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            
            int W=sc.nextInt();
            //容量
            int N=sc.nextInt();
            //代价
            ArrayList<Integer> w=new ArrayList<>();
            //价值
            ArrayList<Integer> v=new ArrayList<>();

            for(int i=0;i<N;i++){
                //数量
                int a=sc.nextInt();
                //体积
                int b=sc.nextInt();
                //价值
                int c=sc.nextInt();
                for(int k=0;k<a;k++){
                    w.add(b);
                    v.add(c);
                }
            }
            N=w.size();
            int[] f=new int[W+1];
            for (int i=0;i<N;i++){
                for(int j=W;j>=w.get(i);j--){
                    //前i个商品对应不同容器的最大价值
                    f[j]=Math.max(f[j],f[j-w.get(i)]+v.get(i));
                }
            }
            System.out.println(f[W]);
        }
    }
}

发表于 2019-06-09 21:12:15 回复(2)