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

背包问题

时间：2023-07-26 22:44:52浏览次数：35  
标签：11 背包 int max 问题 01 include

（1） 01背包

01背包
二维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];//v 保存体积，w 保存价值
int f[N][N];//保存所有集合最值状态

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];

    for(int i = 0; i <= m; i++)//初始化，前 0 中物品中选择
    {
        f[0][i] = 0;
    }

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++)
        {
            if(v[i] <= j)//能放入第 i 件物品的情况下，求f[i][j]
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            else//不能放入第 i 件物品的情况下，求f[i][j]
                f[i][j] = f[i - 1][j];
        }

    }
    cout << f[n][m] << endl;//f[n][m] 就是答案

    return 0;
}

3a840cc2a8d0de1c87783439f101d15.png
从计算公式可以看出，f[i][j] 是由 f[i - 1][j -vi] 和 wi计算出来的。也就是f[i][j]的值是可以从前面已经计算出的 f 值求出来。如果我们能确定 f[i][j] 的一部分初始值，就能通过该公式，一步步计算得出 f[N][V]，也就是我们要找的答案。
一维优化

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
const int N=1010;
int dp[N],w[N],v[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    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]);
    }
    cout<<dp[m];
}

为什么逆序
若j从小到大，f[j-v[i]]中，由于j-v[i]小于j，f[j-v[i]]已经在i这层循环被计算了，而我们想要的f[j-v[i]]应该是i-1层循环里面的，所以j从大到小的话保证此时的f[j-v[i]]还未被计算，也就是第i-1层的数据

举例

4 5
1 2
2 4
3 4
4 5

最大方案是选2和3

如果从前往后遍历，遍历到dp[3]时，dp[3]！＝4，而是在前面被更新为6，所以要从后往前遍历，
也就是第i-1层的数据没有被”污染“

(2) 完全背包

完全背包
没优化前代码

#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ;i ++)
    {
        cin>>v[i]>>w[i];
    }

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

    cout<<f[n][m]<<endl;
}

优化思路
更新次序的内部关系：


f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系： 
			     f[i][j]=max(f[i,j-v]+w , f[i-1][j])

有了上面的关系，那么其实k循环可以不要了(喜新厌旧hh)，核心代码优化成这样：


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

这个代码和01背包的非优化写法很像!!!对比一下，下面是01背包的核心代码


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

两个代码其实只有一句不同（注意下标）


f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

因为和01背包代码很相像，我们很容易想到进一步优化。核心代码可以改成下面这样

 for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }

优化后代码如下

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ;i ++)
    {
        cin>>v[i]>>w[i];
    }

    for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[m]<<endl;
}

(3) 多重背包

1> 未优化

多重背包1
状态转移方程

f[i][j] = max(f[i - 1][j],f[i - 1][j - k * v[i]] + w[i] * k);

和完全背包差不错

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i ++) cin>>v[i]>>w[i]>>s[i];
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= m;j ++){
            for(int k = 0;k <= s[i];k ++){
                if(j >= v[i] * k) f[i][j] = max(f[i][j],f[i - 1][j - k * v[i]] + w[i] * k);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

2>按01背包的扩展来写

多重背包是选一个，两个...到s个，01背包是选和不选

(按01背包写)

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

可以把多重背包中选几个看作为01背包的第i项目选不选
例如
1 2 3
2 4 1
3 4 3
4 5 2
就可以看作为第一个物品选一个，选两个，选三个。三种方案，体积就对应为k*v，价值就是k*w,此时就可当作01背包（后面三个依然如此）

(按正常三重循环)

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

#include<iostream>
#include<cstring>
#include<cstring>

using namespace std;

const int N=110;
int n,m;
int f[N];

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=m;j>=0;j--)
            for(int k=1;k<=s;k++)
            if(j>=k*v)
            f[j]=max(f[j],f[j-k*v]+k*w);
    }
    cout<<f[m];
}

3> 优化版本

#include<iostream>
using namespace std;
const int N=25000;
int f[N],v[N],w[N];
int n,m;
int main()
{
    cin>>n>>m;
    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]=s*a;
            w[cnt]=s*b;
        }
    }
    
    n=cnt;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
}

优化多重背包的优化
首先，我们不能用完全背包的优化思路来优化这个问题，因为每组的物品的个数都不一样，是不能像之前一样推导不优化递推关系的。（因为多重背包数量是有限的）
我们列举一下更新次序的内部关系：

f[i , j ] = max( f[i-1,j] ,   f[i-1,j-v]+w ,    f[i-1,j-2v]+2*w , f[i-1,j-3v]+3*w , .....,f[i-1,j-Sv]+S*w)
f[i , j-v]= max(              f[i-1,j-v] ,      f[i-1,j-2v] + w , f[i-1,j-3v]+2*w , .....,f[i-1,j-Sv]+(S-1)*w,f[i-1,j-(S+1)v]+S*w)
由上两式，可得出如下递推关系：
f[ i ][ j ] = max(f[i,j-v]+w , f[i-1][j])

接下来，我介绍一个二进制优化的方法，假设有一组商品，一共有11个。我们知道，十进制数字 11 可以这样表示

11=1011(B)=0111(B)+(11−0111(B))=0111(B)+0100(B)

正常背包的思路下，我们要求出含这组商品的最优解，我们要枚举12次（枚举装0，1，2....12个）。

现在，如果我们把这11个商品分别打包成含商品个数为1个，2个，4个，4个（分别对应0001,0010,0100,0100）的四个”新的商品 “, 将问题转化为01背包问题，对于每个商品，我们都只枚举一次，那么我们只需要枚举四次 ，就可以找出这含组商品的最优解。 这样就大大减少了枚举次数。

这种优化对于大数尤其明显，例如有1024个商品，在正常情况下要枚举1025次 ， 二进制思想下转化成01背包只需要枚举10次。

优化的合理性的证明
先讲结论：上面的1，2，4，4是可以通过组合来表示出0~11中任何一个数的，还是拿11证明一下（举例一下）：

首先，11可以这样分成两个二进制数的组合：
11=1011(B)=0111(B)+(11−0111(B))=0111(B)+0100(B)
其中0111通过枚举这三个1的取或不取（也就是对0001(B)，0010(B)，0100(B)的组合），可以表示十进制数0~7( 刚好对应了 1，2，4 可以组合出 0~7 ) , 0~7的枚举再组合上0100(B)( 即 十进制的 4 ) ，可以表示十进制数 0~11。其它情况也可以这样证明。这也是为什么，这个完全背包问题可以等效转化为01背包问题，有木有觉得很奇妙
怎么合理划分一个十进制数?
上面我把11划分为

  	     11=1011(B)=0111(B)+(11−0111(B))=0111(B)+0100(B)

是因为 0111(B)刚好是小于11的最大的尾部全为1的二进制 ( 按照上面的证明，这样的划分没毛病 ) , 然后那个尾部全为1的数又可以 分解为 0000....1 , 0000....10 , 0000....100 等等。

(4) 分组背包

分组背包
991d3b14f1d170d856fc817b9f2865f.png

	#include<bits/stdc++.h>
	using namespace std;
	const int N=110;
	int f[N][N];  //只从前i组物品中选，当前体积小于等于j的最大值
	int v[N][N],w[N][N],s[N];   //v为体积，w为价值，s代表第i组物品的个数
	int n,m,k;
	
	int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];  //读入
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];  //不选
            for(int k=0;k<s[i];k++){
                if(j>=v[i][k])     f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<f[n][m]<<endl;
	}

因为数据只用到i-1行的数据，所以要效仿01背包逆序枚举

	#include<bits/stdc++.h>
	using namespace std;
	
	const int N=110;
	int f[N];
	int v[N][N],w[N][N],s[N];
	int n,m,k;
	
	int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }
	
    for(int i=0;i<n;i++){
        for(int j=m;j>=0;j--){
            for(int k=0;k<s[i];k++){    //for(int k=s[i];k>=1;k--)也可以
                if(j>=v[i][k])     f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<f[m]<<endl;
	}

标签：11,背包,int,max,问题,01,include
From： https://www.cnblogs.com/wly040719/p/17583714.html

相关文章

  • 浅谈Excel开发：十 Excel 开发中与线程相关的若干问题
    采用VSTO或者SharedAdd-in等技术开发Excel插件，其实是在与Excel提供的API在打交道，Excel本身的组件大多数都是COM组件，也就是说通过ExcelPIA来与COM进行交互。这其中会存在一些问题，这些问题如果处理不好，通常会导致在运行的时候会抛出难以调试的COM异常，从而导致我们开发出的Excel插......
  • Xcode12 开发12.5.7版本IOS的问题解决
    1.xcode12默认是创建的工程是14.2，所以需要修改一下工程版本。点击项目最上面的蓝色文件就可以打开下面的界面了。2.安装app之后，界面黑屏。解决方法如下：在AppDelegate.h中：#import<UIKit/UIKit.h>@interfaceAppDelegate:UIResponder<UIApplicationDelegate>//增......
  • mysql使用default给列设置默认值的问题
    add column会修改旧的默认值add column和modify column在default的语义上处理不一样。对于addcolumn，会将历史为null的值刷成default指定的值。而对于modifycolumn，只会对新数据产生影响，历史数据仍然会保持为null。结论：1. add column和modify column在default的语义上......
  • Java并发(十三)----共享存在的问题
    1、小故事老王（操作系统）有一个功能强大的算盘（CPU），现在想把它租出去，赚一点外快小南、小女（不同的线程）来使用这个算盘来进行一些计算，并按照时间给老王支付费用但小南不能一天24小时使用算盘，他经常要小憩一会（sleep），又或是去吃饭上厕所（阻塞io操作），有时还需要一根烟，没烟时思路......
  • HashMap非线程安全到底有什么问题
    HashMap是Java中常用的数据结构，用于存储键值对，并且提供了快速的查找和插入操作。下面挖掘一下HashMap内部的架构设计思维：哈希函数的设计：HashMap使用哈希函数将键映射到数组索引上。好的哈希函数应该尽量减少哈希冲突，使得键能够均匀地分布在数组中，从而提高查找效率。Java中的Hash......
  • 01背包
    01背包问题publicclassKnapsackProblem{publicstaticvoidmain(String[]args){int[]w={1,2,3,4,5};int[]value={3,4,6,8,10};intcapacity=10;intn=w.length;ZeroOneKnapsack(w,value,n,capacity);}/**......
  • UG NX实现叉车运输货物功能遇见的问题
    在前一段时间编写模拟叉车运输功能时遇到，货物无法跟随的问题（如下动图）后面发现是速度太快的原因导致货物没有跟着动，类似于抽桌布的感觉解决办法有两种：第一种解决办法很简单就是把速度降低到不超过 200mm/s就可以了（解决后如下图）第二种解决办法是在对速度有高要求的情况下......
  • 问题--链表指针传参，修改next指针只传值
    1.问题--链表指针传参，修改next指针只传值Link_creat_head(&head,p_new);//将新节点加入链表在这当中head头指针传的是地址，而p_new传的是值，这二者有什么区别？#include<stdio.h>#include<stdlib,h>//定义结点结构体typedefstructstudent{//数据域intnum;......
  • 表面着色器的一些问题
    问题①：在表面着色器中修改顶点信息——#pragmasurfacesurfLambertvertex:vert/***********/voidvert(inoutappdata_fullv,outInputo){UNITY_INITIALIZE_OUTPUT(Input,o);/**********/}appdata_full是unity给我们的输入结构体，另外还有一些unity......
  • 英语阅读回答问题技巧
    1、每个问题，要还原到文章具体的某一段落。  若此问题在某段的后半部分，且你没有太看懂，这段已经完事了。要养成一个习惯。接着看一下段的第一句话。实在做不出来的话，就选哪个和下一段第一句话的意思差不多的选项。只能这样了。（貌似是13条的重复）补充下，这只是小技巧，只起补充......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99