首页 > 其他分享 >背包问题

背包问题

时间:2023-04-29 23:01:10浏览次数:42  
标签:背包 int 问题 件物品 体积 物品 dp

背包问题是一种组合优化的NP完全问题. 问题可以描述为: 给定一组物品, 每种物品都有自己的体积和价值, 在限定的总体积内, 我们如何选择, 才能使得物品的总价值最高.


背包九讲

① 01背包问题

N 件物品和一个容量是 V 的背包, 每件物品只能使用一次

i 件物品的体积是 vi , 价值是 wi

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

② 完全背包问题

N 种物品和一个容量是 V 的背包, 每种物品都有无限件可用

i 件物品的体积是 vi , 价值是 wi

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

③ 多重背包问题

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

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

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

④ 混合背包问题

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

物品一共有三类:

第一类物品只能用一次 (01背包)

第二类物品可用无限次 (完全背包)

第三类物品最多只能用 si 次 (多重背包)

i 种物品, 每件体积是 vi , 价值是 wi

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

⑤ 二位费用的背包问题

N 件物品和一个容量是 V 的背包, 背包能承受的最大重量是 M

每件物品只能用一次, 体积是 vi , 重量是 mi , 价值是 wi

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

⑥ 分组背包问题

N 组物品和一个容量是 V 的背包

每组物品有若干个, 同一组内的物品最多只能选一个

每件物品的体积是 vij ,价值是 wij ,其中 i 是组号, j 是组内编号

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

⑦ 有依赖的背包问题(树上背包问题)

N 件物品和一个容量是 V 的背包

物品之间具有依赖关系, 且依赖关系组成一棵树的性质. 如果选择一个物品, 则必须选择它的父节点

每件物品的编号是 i , 体积是 vi , 价值是 wi , 依赖的父节点编号是 pi .物品的下标范围是 1 ~ N

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

⑧ 背包问题求方案数

N 件物品和一个容量是 V 的背包, 每件物品只能用一次

i 件物品的体积是 vi , 价值是 wi

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

输出最优选法的方案数

⑨ 背包问题求具体方案

N 件物品和一个容量是 V 的背包, 每件物品只能用一次

i 件物品的体积是 vi , 价值是 wi

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

输出字典序最小的方案, 这里的字典序是指所选物品的编号所构成的序列, 物品的编号范围是 1 ~ N




01背包问题

//朴素版解法
int dp[N][N];	//dp[i][j]表示前i个物品,背包容量是j的情况下的最大价值
int w[N],v[N];

for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
        dp[i][j]=dp[i-1][j];
        if(j>=v[i])dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
    }

//滚动数组优化
int dp[N];
int v[N],w[N];

for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);



完全背包问题

//朴素版未优化
int dp[N][N];
int v[N],w[N];

for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
        for(int k=0;k*v[i]<=j;k++)
            dp[i][j]==max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);

//朴素解法
int dp[N][N];
int v[N],w[N];

for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
        dp[i][j]=dp[i-1][j];
        if(v[i]<=j)dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
    }

//优化空间版解法
int dp[N];
int v[N],w[N];

for(int i=1;i<=n;i++)
    for(int j=v[i];j<=m;j++)
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);



多重背包问题

//朴素版解法
int dp[N][N];
int v[N],w[N],s[N];

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

二进制优化: 将 s[i] 个物品拆分成 \(log_2\) s[i] 份, 作01背包问题

//二进制优化
int dp[N];
int v[N],w[N];

int cnt=0;
for(int i=1;i<=n;i++)
{
    int a,b,s;
    cin>>a>>b>>s;
    int k=1;
    while(k<=s)
    {
        cnt++;
        v[cnt]=a*k;
        w[cnt]=b*k;
        s-=k;
        k*=2;
    }
    if(s>0)
    {
        cnt++;
        v[cnt]=a*s;
        w[cnt]=b*s;
    }
}
n=cnt;

for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);



混合背包问题

int n,m;				//si=-1表示第i种物品只能用1次
int v[N],w[N],s[N];			//si=0表示第i种物品可以用无限次
int dp[N];				//si>0表示第i种物品可以用si次

struct Good
{
    int kind;
    int v,w;
};

vector <Good> good;

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>v[i]>>w[i]>>s[i];
    for(int i=0;i<n;i++)
    {
        if(s[i]==-1)good.push_back({-1,v[i],w[i]});
        else if(s[i]==0)good.push_back({0,v[i],w[i]});
        else //多重背包二进制优化(分组)后,对于每一组都相当于是01背包
        {
            for(int k=1;k<=s[i];k*=2)
            {
                s[i]-=k;
                good.push_back({-1,v[i]*k,w[i]*k});
            }
            if(s[i]>0)good.push_back({-1,v[i]*s[i],w[i]*s[i]});
        }
    }
    
    //对于01背包和完全背包分两种情况状态转移即可
    for(auto goods:good)
    {
        //01背包
        if(goods.kind==-1)
        {
            for(int j=m;j>=goods.v;j--)
                dp[j]=max(dp[j],dp[j-goods.v]+goods.w);
        }
        //完全背包
		else
        {
            for(int j=goods.v;j<=m;j++)
                dp[j]=max(dp[j],dp[j-goods.v]+goods.w);
        }
    }
    
    cout<<dp[m]<<endl;
    return 0;
}



二位费用的背包问题

//dp[i][j]表示总体积是i,总重量是j的情况下,最大价值是多少
//同时对于状态转移的时候,两层for循环,一层是体积限制,一层是重量限制

int a,b,c;	//a为物品数量,b为背包最大容量,c为背包最大重量
int v[N],t[N],w[N];
int dp[N][N];

for(int i=0;i<a;i++)
    for(j=b;j>=v[i];j--)
        for(int k=c;k>=t[i];k--)
            dp[j][k]=max(dp[j][k],dp[j-v[i]][k-t[i]]+w[i]);



分组背包问题

int dp[N];
int v[N][N],w[N][N],s[N];

for(int i=1;i<=n;i++)
    for(int j=m;j>=0;j--)
        for(int k=0;k<s[i];k++)
            if(v[i][k]<=j)dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);



树上背包问题

特点: N 个物品, V 容量的背包, 物品之间有依赖关系, 且依赖关系可以构成一棵树, 如果选择某一个物品, 那么就必须选择这个物品的父亲物品

父节点编号范围:

内部节点: 1 \(\leqslant\) \(p_i\) \(\leqslant\) N

根节点 \(p_i\) = -1

dp[i][j] 表示选择节点 i (在这里也就是根节点), 总体积是 j 时, 最大价值是多少. 当我们选择根节点后, 对于根节点的每一棵子树, 都相当于对根节点做分组背包了, 每一个根节点相当于一个组, 对于组内的节点分为选择或者不选择


int n,m;
int v[N],w[N];
int dp[N][N];
int h[N],e[N],ne[N],idx;

void add (int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs (int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int son=e[i];
        dfs(son);
        for(int j=m-v[u];j>=0;j--)
            for(int k=0;k<=j;k++)
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k]);
    }
    
    //将根节点u加上
    for(int i=m;i>=v[u];i--)
        dp[u][i]=dp[u][i-v[u]]+w[u];
    //如果选择了子节点后,还没有选择到最后的root,那么就不能选择当前节点及其根节点了
    for(int i=0;i<v[u];i++)
        dp[u][i]=0;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    
    int root;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>v[i]>>w[i]>>p;
        if(p==-1)root=i;
        else add(p,i);
    }
    
    dfs(root);
    cout<<dp[root][m]<<endl;
    return 0;
}



背包问题求方案数

特点: 在背包问题下, 求出最优选法的方案数

f[j] 表示体积恰好是 j 的情况下, 最大价值是多少

g[j] 表示体积恰好是 j 的情况下, 方案数是多少

这个地方的 f[] 数组的含义与前面的背包问题不一样, 所有在这里的初始化, 也与前面不同

f[0 - N] = - \(\infty\) , f[0] = 0 , g[0] = 1


const int mod=1e9+7;
const int INF=0x3f3f3f3f;

int n,m;
int v[N],w[N];
int f[N],g[N];

int main()
{
    cin>>n>>m;
    g[0]=1;
    for(int i=1;i<=m;i++)f[i]=-INF;
    for(int i=0;i<n;i++)cin>>v[i]>>w[i];
    
    for(int i=0;i<n;i++)
        for(int j=m;j>=v[i];j--)
        {
            int t=max(f[j],f[j-v[i]]+w[i]);
            int s=0;
            if(t==f[j])s+=g[j];
            if(t==f[j=v[i]]+w[i])s+=g[j-v[i]];
            if(s>=mod)s-=mod;
            f[j]=t;
            g[j]=s;
        }
    
    int maxx=0;
    for(int i=0;i<=m;i++)maxx=max(maxx,f[i]);
    int ans=0;
    for(int i=0;i<=m;i++)
        if(maxx==f[i])
        {
            ans+=g[i];
            if(ans>=mod)ans-=mod;
        }
    
    cout<<ans<<endl;
    return 0;
}



背包问题求具体方案

特点: 在普通背包的基础下, 输出选择方案

我们要输出所选的方案, 首先我们按照普通背包的问题求解后, 我们会得到 dp[] 数组, 因此如果我们要求出选择了哪一些物品, 我们就可以对 dp[] 数组进行反推

如果 dp[i][j] = dp[i-1][j] , 说明没有选择第 i 个物品

如果 dp[i][j] = dp[i-1][j-v[i]] + w[i] , 说明选择了第 i 个物品

这个题目为了解唯一, 它的答案方案是字典序最小的方案, 因此我们可以按照贪心的思想去做, 如果能选择第 i 个物品, 那么我们就直接选择第 i 个物品, 而不选第 i+1 个物品(如果选择第 i 个物品和第 i+1 个物品所得的最大价值相同的话)

所以正确思路是我们按 n \(\to\) 1 的顺序求解01背包, 接着按 1 \(\to\) n 的顺序反推每个物品是否被选


int n,m;
int v[N],w[N];
int dp[N][N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    
    for(int i=n;i>=1;i--)
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=dp[i+1][j];
            if(j>=v[i])dp[i][j]=max(dp[i][j],dp[i+1][j-v[i]]+w[i]);
        }
    
    int vol=m;
    for(int i=1;i<=n;i++)
        if(vol-v[i]>=0&&dp[i][vol]==dp[i+1][vol-v[i]]+w[i])
        {
            cout<<i<<' ';
            vol-=v[i];
        }
    
    return 0;
}


标签:背包,int,问题,件物品,体积,物品,dp
From: https://www.cnblogs.com/evilboy/p/17364626.html

相关文章

  • z_auto_align G34 probing failed 问题及解决
    目前状况bltouch正常调平检测正常z轴自动对齐,显示probingfailed 原因:刷入新固件后,没有在printer上恢复设置(restoresetting),导致的probeoffset错误 解决方案:多种情况都可能导致该错误,此处仅为其中一种,以作补充刷入固件后检查以下probe......
  • 问题解决:Component name "xxx" should always be multi-word vue/multi-word-compone
    如题,原因是单个单词命名时语法检测无法通过,可以在导出组件时通过name属性给组件名加一个后缀,比如Component。<script>exportdefault{//当组件名为一个单词时,语法检查是无法通过的,可以设置name的值为2个单词来规避检查。name:'HomeComponent'}<......
  • IdentityServer4 问题解决
    RedirectUris={"https://localhost:7098/signin-oidc"},PostLogoutRedirectUris={"https://localhost:7098/signout-callback-oidc"},服务端添加这个 RequirePkce=false,添加这一句......
  • thymeleaf学习问题整理
    使用配置<properties><java.version>1.8</java.version><thymeleaf.version>3.0.9.RELEASE</thymeleaf.version><thymeleaf-layout-dialect.version>2.2.2</thymeleaf-layout-dialect.version></p......
  • 06 - react的类组件中的状态state render函数 this指向问题 事件绑定
    //注册事件importReactDomfrom"react-dom"import{Component}from"react"//类组件中的状态通过this.state.xxx来获取状态classHelloextendsComponent{//事件对象eventhandleClick(e){console.log(this)//udnefiend使用箭头函数解决this......
  • open3d Reconstruction system 问题解决
    1.https://github.com/luckyluckydadada/Azure-Kinect-DK-3D-reconstruction 2.open3d版本:0.14.10.16.00.17.0会报错:open3d.cuda.pybind.piplines.odommetry.OdomtryOptionbojecthasnoattribute'max_depth_diff' 3.结果问题一:    根据......
  • refusing to merge unrelated histories问题的解决
    问题描述将代码从云端拉取到本地,出现了这个错误,说我这里无法合并并不相关的历史,然后就屁颠屁颠地去找报错原因去了问题解决输入gitpulloriginmain--allow-unrelated-histories即,合并并不相关的分支,即便并不相关!然后,错误成功解决啦!......
  • fatal: couldn't find remote ref master问题的解决
    问题描述在写入决定合并并不相关的分支的代码之后,就又出现了这个报错,就很离谱,麻了呀家人们!问题解决gitpulloriginmaster--allow-unrelated-histories,这个命令执行错误,是因为,我这里的分支名称不叫作master,叫做main旧版默认为master;新版改成main啦!各位注意嘞!......
  • 昆仑通态问题
      控件写,定义一个开关变量,通过开关变量控制不让用户输入。 还用一种方式不让用户输入和点击,拖一个按钮,拉大当成panel,设置透明,挡在其他控件前面。   控件名复制: ......
  • 连通区域(Connected Components)问题
    packagemain.java.test;importjava.util.Arrays;importjava.util.Scanner;publicclasst5{publicstaticvoidmain(String[]args){//Scannersc=newScanner(System.in);//Strings=sc.nextLine();Strings="35&qu......