51nod 1086 多重背包模板

叁歲伎倆 2022-08-19 15:19 163阅读 0赞

有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数）。求背包能够容纳的最大价值。

#include <iostream>
    #include <cstring>
    #include <cmath>
    #include <string>
    #include<cstring>
    using namespace std;
    
    const int SIZE = 50001;
    long long dp[SIZE],volume[101],value[101],c[101];
    int n,v;          //总物品数，背包容量
    
    void ZeroOnepark(int val,int vol)
    {     //01背包
    	for (int j =v ;j >= vol;j-- )
    	{
    		dp[j]=max(dp[j],dp[j-vol]+val);
    	}
    }
    
    void Completepark(int val,int vol)
    {      //完全背包
    	for (int j =vol;j <= v;j++ )
    	{
    		dp[j]=max(dp[j],dp[j-vol]+val);
    	}
    }
    
    void Multiplepark(int val,int vol,int amount)
    {    //多重背包
    	if (vol*amount >= v)  Completepark(val,vol);
    	else{
    		int k = 1;
    		while (k < amount)
    		{
    			ZeroOnepark(k * val, k * vol);
    			amount -= k;
    			k <<= 1;
    		}
    		if (amount > 0) {
    			ZeroOnepark(amount * val, amount * vol);
    		}
    	}
    }
    
    int main()
    {
    	while (cin>>n>>v)
    	{
    		for (int i = 1 ; i <= n ; i++)
    		{
    			cin>>volume[i]>>value[i]>>c[i];      //费用，价值，数量
    		}
            memset(dp,0,sizeof(dp));
    		for (int i = 1;i <= n;i++)
    		{
    			Multiplepark(value[i],volume[i],c[i]);
    		}
    		cout<<dp[v]<<endl;
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，163人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod1136 欧拉函数模板

[1136 欧拉函数][1136] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [1136]: http://www.51nod.com/online

悠悠/ 2024年02月17日 23:17/ 0 赞/ 103 阅读

相关 51Nod 1086 背包问题 V2(二进制多重背包)

知识点：Cn=1+2+4+8+.....+ 2^(m-2)+t。我们可以检验，在\[1,Cn\]中任意的数我们都可以在这个序列中找到若干数相加得到。 [1086 背包问题

一时失言乱红尘/ 2024年02月17日 19:19/ 0 赞/ 50 阅读

相关多重背包

POJ1014 http://poj.org/problem?id=1014 该题目就是用的多重背包的思路，若要平分一堆东西，那就以东西价值的一半作为背包容量，看是否刚好能装

迈不过友情╰/ 2023年06月07日 05:53/ 0 赞/ 47 阅读

相关 51nod 1007 正整数分组（类01背包问题）

将一堆正整数分为2组，要求2组的和相差最小。例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。这道题就是要

Love The Way You Lie/ 2022年08月20日 12:29/ 0 赞/ 159 阅读

相关 51nod 1085 01背包模板

在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。

我就是我/ 2022年08月19日 15:19/ 0 赞/ 224 阅读

相关 51nod 1086 多重背包模板

有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P

叁歲伎倆/ 2022年08月19日 15:19/ 0 赞/ 164 阅读

相关多重背包

问题：一个容量为c的背包，还有一些物品（每个物品有具体的数量num），这些物品的体积w和价值v各不相同。求出能在不超过c的情况下尽可能的使价值最大。对于多重背包问题，可

妖狐艹你老母/ 2022年05月31日 01:19/ 0 赞/ 261 阅读

相关 01，完全，多重背包模板

//01背包模板 //假设a[i]代表质量，b[i]代表价值,dp[n]代表在背包大小为n时的最优解 //n代表物品数量，m代表背包大小 //

Love The Way You Lie/ 2022年05月29日 10:24/ 0 赞/ 275 阅读

相关 51nod1085背包问题

[51Nod - 1085][] [1085 背包问题][1085] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [难度：

不念不忘少年蓝@/ 2022年05月22日 08:55/ 0 赞/ 162 阅读

相关多重背包

n个物品，每个可以取k次，容量为w，价值为v。一般做法：二进制拆分：将每个物品拆成O(log k)个01背包的物品，时间复杂度为(nmlogk) 例如：K=10 可以拆分

矫情吗；*/ 2021年12月23日 11:05/ 0 赞/ 380 阅读