• 背包问题及其拓展

    目录

    01背包

    1. 采药

    2. 装箱问题

    3.开心的金明

    二维背包

    1. 二维费用的背包问题

     2. 宠物小精灵之收服

    3.潜水员【01背包问题+二维费用'不少于'问题】 

     分组背包 

    机器分配【分组背包+背包DP输出方案—拓扑图分析】

    有依赖的背包问题 

    有依赖的背包问题【有依赖背包DP+子物品体积集合划分】

    金明的预算方案【有依赖背包DP+分组背包集合划分】

    背包问题求解方案数 

    1.背包问题求解方案数 【背包DP求最优方案总数】

    2. 数字组合【01背包求解方案数】

    3.买书【完全背包求解方案数+朴素优化】

    4. 货币系统【完全背包求解方案数】 

     5.货币系统【完全背包求解最大无关向量组个数】

    背包问题求具体方案 

    背包问题求具体方案【01背包 + 背包DP输出方案】

    多重背包问题

    1. 多重背包问题 III【单调队列优化+图示】 

    二维朴素版 

     一维优化

    庆功会【多重背包朴素版】  

    朴素写法

     一维优化

     混合背包问题

    混合背包问题【混合背包DP模型】

    其他背包问题

    能量石【01背包 + 贪心（邻项交换）】

     

    01背包

    1. 采药

    题目 采药 

    1. #include
    2. using namespace std;
    3. const int N=1e3+10;
    4. int f[N];//滚动数组优化后的
    5. int main()
    6. {
    7.     int n,m;
    8.     cin>>m>>n;
    9.     for(int i=0;i
    10.     {
    11.         int v,w;
    12.         cin>>v>>w;
    13.         for(int j=m;j>=v;j--) f[j]=max(f[j],f[j-v]+w);//从打到小滚动，要么选当前数，要么不选
    14.     }
    15.     cout<
    16.     return 0;
    17. }

    2. 装箱问题

    题目 装箱问题

    1. #include
    2. using namespace std;
    3. const int N=2e4+10;
    4. int f[N];
    5. int main()
    6. {
    7.     int n,m;
    8.     cin>>m>>n;
    9.     for(int i=0;i
    10.     {
    11.         int v;
    12.         cin>>v;
    13.         for(int j=m;j>=v;j--) f[j]=max(f[j],f[j-v]+v);
    14.     }
    15.     cout<
    16.     return 0;
    17. }

    3.开心的金明

    题目 开心的金明

    1. #include
    2. using namespace std;
    3. const int N=3e4+10;
    4. int f[N];
    5. int main()
    6. {
    7.    int n,m;
    8.    cin>>m>>n;
    9.    for(int i=1;i<=n;i++)
    10.    {
    11.        int v,w;
    12.        cin>>v>>w;
    13.        for(int j=m;j>=v;j--)
    14.          f[j]=max(f[j],f[j-v]+v*w);
    15.    }
    16.    cout<
    17.    return 0;
    18. }

    二维背包

    1. 二维费用的背包问题

    题目 二维费用的背包问题

    1. #include
    2. using namespace std;
    3. const int N=1e4+10;
    4. int f[N][N];
    5. int main()
    6. {
    7.    int n,b,c;
    8.    scanf("%d%d%d",&n,&b,&c);
    9.    for(int i=1;i<=n;i++) {
    10.        int v,m,w;
    11.        scanf("%d%d%d",&v,&m,&w);
    12.     for(int j=b;j>=v;j--)//优化一维
    13.       for(int k=c;k>=m;k--)
    14.        f[j][k]=max(f[j][k],f[j-v][k-m]+w);//要么选第i个，要么不选第i个
    15.    }
    16.    printf("%d",f[b][c]);
    17.    return 0;
    18. }

     2. 宠物小精灵之收服

    题目 宠物小精灵之收服

    初始状态：f[0][0][0]
    目标状态：f[n][m][t - 1] （皮神不能 再起不能 才算抓住那个 宝可梦 ） 

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. const int N = 110, M = 1010, K = 510;
    8.  
    9. int n, m, t;
    10. int v1[N], v2[N];
    11. int f[M][K];
    12.  
    13. int main()
    14. {
    15.     //input
    16.     cin >> m >> t >> n;
    17.     for (int i = 1; i <= n; ++ i) cin >> v1[i] >> v2[i];
    18.  
    19.     //dp
    20.     for (int i = 1; i <= n; ++ i)
    21.     {
    22.         for (int j = m; j >= v1[i]; -- j)
    23.         {
    24.             for (int k = t - 1; k >= v2[i]; -- k)
    25.             {
    26.                 f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
    27.             }
    28.         }
    29.     }
    30.  
    31.     //output
    32.     cout << f[m][t - 1] << " ";
    33.     //找到满足最大价值的所有状态里，第二维费用消耗最少的
    34.     int cost_health = t;
    35.     for (int k = 0; k <= t - 1; ++ k)
    36.     {
    37.         if (f[m][k] == f[m][t - 1])
    38.         {
    39.             cost_health = min(cost_health, k);
    40.         }
    41.     }
    42.     cout << t - cost_health << endl;
    43.     return 0;
    44. }
    45.

    3.潜水员【01背包问题+二维费用'不少于'问题】 

    题目 潜水员

    1. #include
    2. using namespace std;
    3. const int N=22,M=80;
    4. int f[N][M];
    5. int main()
    6. {
    7.   int V1,V2,n;
    8.   cin>>V1>>V2>>n;
    9.   memset(f,0x3f,sizeof f);//求最小值要把除初始状态以外的所有状态初始化为+∞
    10.   f[0][0]=0;//表示前0个物品选第一个体积V1至少为0的,第二个体积V2至少为0的价值为0，而其他不存在初始化为正无穷，表示更新最小值不用到他
    11.   for(int i=1;i<=n;i++)
    12.   {
    13.       int v1,v2,w;
    14.       cin>>v1>>v2>>w;
    15.       for(int j=V1;j>=0;j--)
    16.         for(int k=V2;k>=0;k--)
    17.            f[j][k]=min(f[j][k],f[max(0,j-v1)][max(0,k-v2)]+w);//假如小于0，就让他等于0
    18.   }
    19.   cout<//输出至少为V1和V2的最小价值
    20.    return 0;
    21. }

     分组背包 

    机器分配【分组背包+背包DP输出方案—拓扑图分析】

    题目 机械分配
     

     

    1. #include
    2. using namespace std;
    3. const int N=15,M=20;
    4. int f[N][M],v[N][M],w[M];//用v存第i组物品的各物品数的分别价值，w存的是每组物品分别用到那个
    5. int main()
    6. {
    7. 	int n,m;
    8. 	cin>>n>>m;
    9. 	for(int i=1;i<=n;i++)
    10. 	for(int j=1;j<=m;j++)
    11. 	cin>>v[i][j];
    12. 	for(int i=1;i<=n;i++)
    13. 	for(int j=1;j<=m;j++)
    14. 	for(int k=0;k<=j;k++)
    15. 	f[i][j]=max(f[i-1][k]+v[i][j-k],f[i][j]);
    16. 	cout<
    17. 	for(int i=n,j=m;i>=1;i--)
    18. 	for(int k=0;k<=j;k++)
    19. 	{
    20. 		if(f[i][j]==f[i-1][k]+v[i][j-k])
    21. 		{
    22. 			w[i]=j-k;
    23. 			j=k;
    24. 			break;
    25. 		}
    26. 		
    27. 	}
    28.  
    29. 	for(int i=1;i<=n;i++)
    30. 	cout<" "<
    31. }

    1. ​
    2. #include
    3. using namespace std;
    4. const int N=15,M=20;
    5. int f[N][M],v[N][M],flag[N][M];//存每个公司被分配的设备数 
    6. void dfs(int x,int y)
    7. {
    8. 	if(x==0)return;
    9. 	dfs(x-1,y-flag[x][y]);
    10. 	cout<" "<
    11. }
    12. int main()
    13. {
    14. 	int n,m;
    15. 	cin>>n>>m;
    16. 	for(int i=1;i<=n;i++)
    17. 	for(int j=1;j<=m;j++)
    18. 	cin>>v[i][j];
    19. 	for(int i=1;i<=n;i++)
    20. 	for(int j=1;j<=m;j++)
    21. 	for(int k=0;k<=j;k++)
    22. 	{
    23. 		if(f[i][j]-1][k]+v[i][j-k])
    24. 		{
    25. 			f[i][j]=f[i-1][k]+v[i][j-k];
    26. 			flag[i][j]=j-k;//存第i个公司被分配的j-k个设备 
    27. 		}
    28. 		  
    29. 	}
    30. 	cout<
    31.  	dfs(n,m); 
    32. }
    33.  
    34. ​

    有依赖的背包问题 

    有依赖的背包问题【有依赖背包DP+子物品体积集合划分】

    题目有依赖的背包问题

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 110;
    7.  
    8. int n, m, root;
    9. int h[N], e[N], ne[N], idx;
    10. int v[N], w[N];
    11. int f[N][N];
    12.  
    13.  
    14. void add(int a, int b)
    15. {
    16.     e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    17. }
    18. void dfs(int u)
    19. {
    20.     //先枚举所有状态体积小于等于j-v[u]的所有子节点们能够获得的最大价值
    21.     for (int i = h[u]; i!=-1; i = ne[i])
    22.     {
    23.         int son = e[i];
    24.         dfs(son); //从下往上算，先计算子节点的状态
    25.         for (int j = m - v[u]; j >= 0; -- j) //枚举所有要被更新的状态
    26.         {
    27.             for (int k = 0; k <= j; ++ k)   //枚举该子节点在体积j下能使用的所有可能体积数
    28.             {
    29.                 f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    30.             }
    31.         }
    32.     }
    33.     //最后选上第u件物品
    34.     for (int j = m; j >= v[u]; -- j) f[u][j] = f[u][j - v[u]] + w[u];
    35.     for (int j = 0; j <  v[u]; ++ j) f[u][j] = 0;   //清空没选上u的所有状态
    36. }
    37. int main()
    38. {
    39.     memset(h, -1, sizeof h);
    40.     cin >> n >> m;
    41.     for (int i = 1; i <= n; ++ i)
    42.     {
    43.         int p;
    44.         cin >> v[i] >> w[i] >> p;
    45.         if (p == -1) root = i;
    46.         else add(p, i);
    47.     }
    48.     dfs(root);
    49.     cout << f[root][m] << endl;
    50.     return 0;
    51. }

    金明的预算方案【有依赖背包DP+分组背包集合划分】

    题目 金明的预算方案

    解析

    1. #include
    2. using namespace std;
    3. #define x first
    4. #define y second
    5. typedef pair<int,int> PII;
    6. const int N=65,M=32010;
    7. int f[M],v,w,q;
    8. PII zhu[N];//用来存主件
    9. vector fu[N];//用来附件主件
    10. int main()
    11. {
    12.     int m,n;
    13.     cin>>m>>n;
    14.     for(int i=1;i<=n;i++)
    15.     {
    16.         cin>>v>>w>>q;
    17.         if(!q)
    18.         zhu[i]={v,v*w};//把主件放进去
    19.         else
    20.         fu[q].push_back({v,v*w});//把附件存该主件下
    21.     }
    22.     for(int i=1;i<=n;i++)
    23.     {
    24.         if(zhu[i].x)
    25.         for(int j=m;j>=0;j--)
    26.         {
    27.         
    28.             int t=fu[i].size();
    29.            for(int k=0;k<1<//二进制枚举在附件有t个的情况下的选法
    30.            {
    31.                int v=zhu[i].x,w=zhu[i].y;
    32.                 for(int u=0;u//枚举位数，判断该位数是否为1，为1则选该附件
    33.                  if(k>>u&1) v+=fu[i][u].x,w+=fu[i][u].y;
    34.                if(j>=v) f[j]=max(f[j],f[j-v]+w);//假如合法，则转移
    35.            }
    36.         }
    37.     }
    38.     cout<
    39. }

    背包问题求解方案数 

    1.背包问题求解方案数 【背包DP求最优方案总数】

    背包问题求解方案数 

    1. #include
    2. using namespace std;
    3. const int N=1010,mod=1e9+7;
    4. int f[N],cnt[N];
    5. int main()
    6. {
    7. 	int n,m;
    8. 	cin>>n>>m;
    9. 	for(int i=0;i<=m;i++)
    10. 	cnt[i]=1;
    11. 	for(int i=1;i<=n;i++)
    12. 	{
    13. 		int v,w;
    14. 		cin>>v>>w;
    15. 		for(int j=m;j>=v;j--)
    16. 		{
    17. 			int value=f[j-v]+w;
    18. 			if(value>f[j])
    19. 			{
    20. 				cnt[j]=cnt[j-v];
    21. 				f[j]=value;
    22. 			}
    23. 			else if(value==f[j])
    24. 			{
    25. 				 cnt[j]=(cnt[j]+cnt[j-v])%mod;
    26. 			}
    27. 		}
    28. 	}
    29. 	cout<
    30. }

    2. 数字组合【01背包求解方案数】

    题目 数字组合
     

    分析
    对于本题我们可以把每个 正整数 看作是一个 物品

    正整数 的值就是 物品 的 体积

    我们方案选择的 目标 是最终 体积 恰好为 m 时的 方案数

    于是本题就变成了 01背包求解方案数 的问题了

    闫氏DP分析法
    初始状态：f[0][0]

    目标状态：f[n][m]

    1. #include
    2. using namespace std;
    3. const int N=110,M=10010;
    4. int f[M],v[N];
    5. int main()
    6. {
    7.     int n,m;
    8.     cin>>n>>m;
    9.     for(int i=1;i<=n;i++)
    10.     cin>>v[i];
    11.     f[0]=1;
    12.     for(int i=1;i<=n;i++)
    13.     for(int j=m;j>=v[i];j--)
    14.     f[j]+=f[j-v[i]];
    15.     cout<
    16. }


    3.买书【完全背包求解方案数+朴素优化】

    题目 买书 

    初始状态：f[0][0]

    目标状态：f[n][m]


    Code（朴素版）
    最坏时间复杂度：O(n^2×m)

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 5, M = 1010;
    6.  
    7. int n = 4, m;
    8. int v[N] = {0, 10, 20, 50, 100};
    9. int f[N][M];
    10.  
    11. int main()
    12. {
    13.     //input
    14.     cin >> m;
    15.  
    16.     //dp
    17.     f[0][0] = 1;
    18.     for (int i = 1; i <= n; ++ i)
    19.     {
    20.         for (int j = 0; j <= m; ++ j)
    21.         {
    22.             for (int k = 0; v[i] * k <= j; ++ k)
    23.             {
    24.                 f[i][j] += f[i - 1][j - v[i] * k];
    25.             }
    26.         }
    27.     }
    28.  
    29.     //output
    30.     cout << f[n][m] << endl;
    31.  
    32.     return 0;
    33. }

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 5, M = 1010;
    6.  
    7. int n = 4, m;
    8. int v[N] = {0, 10, 20, 50, 100};
    9. int f[M];
    10.  
    11. int main()
    12. {
    13.     //input
    14.     cin >> m;
    15.  
    16.     //dp
    17.     f[0] = 1;
    18.     for (int i = 1; i <= n; ++ i)
    19.     {
    20.         for (int j = v[i]; j <= m; ++ j)
    21.         {
    22.             f[j] += f[j - v[i]];
    23.         }
    24.     }
    25.  
    26.     //output
    27.     cout << f[m] << endl;
    28.  
    29.     return 0;
    30. }
    31.

    4. 货币系统【完全背包求解方案数】 

    题目 货币系统

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. typedef long long LL;
    6.  
    7. const int N = 20, M = 3010;
    8.  
    9. int n, m;
    10. int v[N];
    11. LL f[M];
    12.  
    13. int main()
    14. {
    15.     cin >> n >> m;
    16.     for (int i = 1; i <= n; ++ i) cin >> v[i];
    17.     f[0] = 1;
    18.     for (int i = 1; i <= n; i++)
    19.     {
    20.         for (int j = v[i]; j <= m; j++)
    21.         {
    22.             f[j] += f[j - v[i]];
    23.         }
    24.     }
    25.     cout << f[m] << endl;
    26.     return 0;
    27. }
    28.

     5.货币系统【完全背包求解最大无关向量组个数】

    题目 货币系统

    解析

    1. #include
    2. using namespace std;
    3.  
    4. //这题是一道线性代数问题
    5. //求解一个向量组的秩(最大无关向量组的向量个数)
    6. //但是代码写起来就是一个模拟筛的过程
    7. //从小到大，先查看当前数有没有被晒掉，
    8. //1)如果没有就把它加入到最大无关向量组中，并把他以及他和此前的硬币的线性组合都筛掉
    9. //2)如果有就不理会
    10. //即就是在完全背包求方案数的过程中，统计那些初始没有方案数的物品
    11. //这样就变成一个完全背包问题了
    12.  
    13. const int N = 110, M = 25010;
    14. int n;
    15. int v[N];
    16. bool f[M];
    17.  
    18. int main()
    19. {
    20.     int T = 1;
    21.     cin >> T;
    22.     while (T -- )
    23.     {
    24.         cin >> n;
    25.         for (int i = 1; i <= n; ++ i) cin >> v[i];
    26.         sort(v + 1, v + n + 1);//排序的原因见之前的分析
    27.  
    28.         //我们只需统计所有物品的体积是否能被其他的线性表出
    29.         //因此背包的体积只需设置为最大的物品体积即可
    30.         //res用来记录最大无关向量组的个数
    31.         int m = v[n], res = 0;
    32.         memset(f, 0, sizeof f);
    33.         f[0] = true;    //状态的初值
    34.         for (int i = 1; i <= n; ++ i)
    35.         {
    36.             //如果当前物品体积被之前的物品组合线性筛掉了，则它是无效的
    37.             if (f[v[i]]) continue;
    38.             //如果没有被筛掉，则把它加入最大无关向量组
    39.             res ++ ;
    40.             //筛掉当前最大无关向量组能线性表示的体积
    41.             for (int j = v[i]; j <= m; ++ j)
    42.             {
    43.                 f[j] |= f[j - v[i]];
    44.             }
    45.         }
    46.         //输出最大无关向量组的向量个数
    47.         cout << res << endl;
    48.     }
    49.     return 0;
    50. }

    背包问题求具体方案 

    背包问题求具体方案【01背包 + 背包DP输出方案】

    背包问题求具体方案 

    题解

    1. #include
    2. using namespace std;
    3. const int N=1010;
    4. int f[N][N];
    5. int v[N],w[N];
    6. int main()
    7. {
    8. 	int n,m;
    9. 	cin>>n>>m;
    10. 	for(int i=1;i<=n;i++)
    11. 	cin>>v[i]>>w[i];
    12. 	for(int i=n;i;i--)
    13. 	for(int j=0;j<=m;j++)
    14. 	{
    15. 		f[i][j]=f[i+1][j];
    16. 		if(j>=v[i])
    17. 		f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
    18. 	}
    19. 	int i=1,j=m;
    20. 	while(i<=n)
    21. 	{
    22. 		if(j>=v[i]&&f[i+1][j-v[i]]+w[i]>=f[i+1][j])
    23. 		{
    24. 			cout<" ";
    25. 			j-=v[i];
    26. 			i++;
    27. 		}
    28. 		else i++;
    29. 	}
    30. 	
    31. 	
    32. }

    多重背包问题

    1. 多重背包问题 III【单调队列优化+图示】 

    题目 多重背包问题 Ⅲ

    详细解析

    二维朴素版 

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 1010, M = 20010;
    6.  
    7. int n, m;
    8. int v[N], w[N], s[N];
    9. int f[N][M];
    10. int q[M];
    11.  
    12. int main()
    13. {
    14.     cin >> n >> m;
    15.     for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    16.     for (int i = 1; i <= n; ++ i)
    17.     {
    18.         for (int r = 0; r < v[i]; ++ r)
    19.         {
    20.             int hh = 0, tt = -1;
    21.             for (int j = r; j <= m; j += v[i])
    22.             {
    23.                 while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
    24.                 while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j]) -- tt;
    25.                 q[ ++ tt] = j;
    26.                 f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
    27.             }
    28.         }
    29.     }
    30.     cout << f[n][m] << endl;
    31.     return 0;
    32. }
    33.  
    34.

     一维优化

    拷贝数组

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 1010, M = 20010;
    7.  
    8. int n, m;
    9. int v[N], w[N], s[N];
    10. int f[M], g[M];
    11. int q[M];
    12.  
    13. int main()
    14. {
    15.     cin >> n >> m;
    16.     for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    17.     for (int i = 1; i <= n; ++ i)
    18.     {
    19.         memcpy(g, f, sizeof g);
    20.         for (int r = 0; r < v[i]; ++ r)
    21.         {
    22.             int hh = 0, tt = -1;
    23.             for (int j = r; j <= m; j += v[i])
    24.             {
    25.                 while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
    26.                 while (hh <= tt && g[q[tt]] + (j - q[tt]) / v[i] * w[i] <= g[j]) -- tt;
    27.                 q[ ++ tt] = j;
    28.                 f[j] = g[q[hh]] + (j - q[hh]) / v[i] * w[i];
    29.             }
    30.         }
    31.     }
    32.     cout << f[m] << endl;
    33.     return 0;
    34. }

    滚动数组

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 1010, M = 20010;
    6.  
    7. int n, m;
    8. int v[N], w[N], s[N];
    9. int f[2][M];
    10. int q[M];
    11.  
    12. int main()
    13. {
    14.     cin >> n >> m;
    15.     for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    16.     for (int i = 1; i <= n; ++ i)
    17.     {
    18.         for (int r = 0; r < v[i]; ++ r)
    19.         {
    20.             int hh = 0, tt = -1;
    21.             for (int j = r; j <= m; j += v[i])
    22.             {
    23.                 while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
    24.                 while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) -- tt;
    25.                 q[ ++ tt] = j;
    26.                 f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
    27.             }
    28.         }
    29.     }
    30.     cout << f[n & 1][m] << endl;
    31.     return 0;
    32. }
    33.

    庆功会【多重背包朴素版】  

    题目 庆功会

    朴素写法

    1.  
    2. #include
    3. using namespace std;
    4. const int N=510,M=6010;
    5. int f[N][M],v[N];
    6. int main()
    7. {
    8. 	int n,m;
    9. 	cin>>n>>m;
    10. 	for(int i=1;i<=n;i++)
    11. 	{
    12. 		int v,w,s;
    13. 		cin>>v>>w>>s;
    14. 		for(int j=1;j<=m;j++)
    15. 		for(int k=0;k<=s&&k*v<=j;k++)
    16. 		f[i][j]=max(f[i][j],f[i-1][j-k*v]+k*w);
    17. 	}
    18. 	cout<
    19. }

     一维优化

    1. #include
    2. using namespace std;
    3. const int N=510,M=6010;
    4. int f[M],v[N];
    5. int main()
    6. {
    7. 	int n,m;
    8. 	cin>>n>>m;
    9. 	for(int i=1;i<=n;i++)
    10. 	{
    11. 		int v,w,s;
    12. 		cin>>v>>w>>s;
    13. 		for(int j=m;j>=v;j--)
    14. 		for(int k=0;k<=s&&k*v<=j;k++)
    15. 		f[j]=max(f[j],f[j-k*v]+k*w);
    16. 	}
    17. 	cout<
    18. }

     混合背包问题

    混合背包问题【混合背包DP模型】

    题目 

    解析

    1. #include
    2. using namespace std;
    3. const int N=1010;
    4. int f[N];
    5. struct Thing
    6. {
    7. 	int kind;
    8. 	int v,w;
    9. };
    10. vector things;
    11. int main()
    12. {
    13. 	int n,m;
    14. 	cin>>n>>m;
    15. 	for(int i=0;i
    16. 	{
    17. 		int v,w,s;
    18. 		cin>>v>>w>>s;
    19. 		if(s<0) things.push_back({-1,v,w});
    20. 		else if(s==0) things.push_back({0,v,w});
    21. 		else
    22. 		{
    23. 			for(int k=1;k<=s;k*=2)
    24. 			{
    25. 				s-=k;
    26. 				things.push_back({-1,v*k,w*k});
    27. 			}
    28. 			if(s>0)things.push_back({-1,v*s,w*s});
    29. 		}
    30. 	}
    31. 	for(auto thing : things)
    32. 	{
    33. 		if(thing.kind<0)
    34. 		for(int j=m;j>=thing.v;j--)
    35. 		f[j]=max(f[j],f[j-thing.v]+thing.w);
    36. 		else
    37. 		for(int j=thing.v;j<=m;j++)
    38. 		f[j]=max(f[j],f[j-thing.v]+thing.w);
    39. 	}
    40. 	cout<
    41. }

    其他背包问题

    能量石【01背包 + 贪心（邻项交换）】

    题目 能量石

    解析 

    1. #include
    2. using namespace std;
    3. const int N=110,M=1e5+10;
    4. int f[M];
    5. struct Node
    6. {
    7.     int s,e,l;
    8.     bool operator<(const Node &x)const //重载小于号
    9.     {
    10.         return  s*x.l
    11.     }
    12. }a[N];
    13. void solve()
    14. {
    15.     int t=0;//存储总时间
    16.     //求恰好的背包DP,为了保证状态都是从起点转移的,要把非起点初始化为无穷大以避免转移
    17.     memset(f, -0x3f, sizeof f);
    18.     f[0] = 0;
    19.     int n;
    20.     cin>>n;
    21.     for(int i=1;i<=n;i++)
    22.     {
    23.         cin>>a[i].s>>a[i].e>>a[i].l;
    24.         m+=a[i].s;
    25.     }
    26.     sort(a+1,a+n+1);
    27.         for(int i=1;i<=n;i++)
    28.         {
    29.             for(int j=m;j>=a[i].s;j--)
    30.             {
    31.                 f[j]=max(f[j],f[j-a[i].s]+max(0,a[i].e-(j-a[i].s)*a[i].l));
    32.             }
    33.         }
    34.         int res=0;
    35.         for(int i=1;i<=m;i++)  res=max(res,f[i]);
    36.         cout<
    37. }
    38. int main()
    39. {
    40.     int t;
    41.     cin>>t;
    42.     for(int i=1;i<=t;i++)
    43.     {
    44.         cout<<"Case #"<": ";
    45.         solve();
    46.     }
    47. }

  • 相关阅读:
    BP神经网络算法基本原理,bp神经网络的算法步骤
    【教程】uni-app iOS打包解决profile文件与私钥证书不匹配问题
    聚已内酯共聚肝素 Heparin-PCL/聚乳酸-羟基乙酸共聚物-b-肝素 Heparin-PLGA/聚乳酸-b-肝素 Heparin-PLA
    C++基础语法（继承）
    外贸人如何把握客户跟进频率？
    Springboot毕设项目基于SpringBoot的图片网站f3yv9（java+VUE+Mybatis+Maven+Mysql）
    基于信息融合的风电机组关键部件状态识别
    Java高并发编程实战3，Java内存模型与Java对象结构
    HTTP与SOCKS-哪种协议更适合您的代理需求？
    如何检测Windows服务停止后自动启动？自动运行.bat批处理文件？
  • 原文地址：https://blog.csdn.net/m0_64378422/article/details/127769279