首页 > 其他 > 详细

多重背包的二进制优化方法

时间:2020-05-07 19:51:29      阅读:66      评论:0      收藏:0      [点我收藏+]

题目描述:

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

输出格式
输出一个整数,表示最大价值。

当多重背包问题数据规模比较大的时候,我们可以采用二进制优化方法

代码如下:

#include<iostream>
#include<vector>
using namespace std;
const int N=2010;
int n,m;
int f[N];
struct Good{
    int v,w;//货物的价值和体积 
};  
int main()
{
    vector<Good> goods;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int k=1;k<=s;k*=2)
        {
            s-=k;
            //更新改变之后价值和体积,把大范围的东西慢慢的缩小 
            goods.push_back({v*k,w*k});
        }
        if(s>0) goods.push_back({v*s,w*s});//处理剩下的 
     } 
     
     //auto 是一个类型说明符,通过变量的初始值来判断变量的类型 
     //这里需要熟悉下静态变量和自动变量的区别 
     for(auto good:goods)
     for(int j=m;j>=good.v;j--)//转换为01背包问题 
     f[j]=max(f[j],f[j-good.v]+good.w);
     cout<<f[m]<<endl;
     return 0;
}

 

多重背包的二进制优化方法

原文:https://www.cnblogs.com/hrlsm/p/12845033.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!