动态规划 是对解最优化问题的一种途径 它往往是针对一种最优化问题 根据问题的不同性质 确定不同的设计方法
因为这篇文章我想说点关于背包问题的事情 所以不再过多介绍动态规划
背包问题 是动态规划中的一个经典题型 在联赛中也经常出现 其基本问题主要分为01 完全 多重 三种
下面就通过程序与例题分别来说一下三种基本问题
01背包
有n件物品和容量为m的背包 给出i件物品的重量以及价值 求解让装入背包的物品重量不超过背包容量 且价值最大
特点 这是最简单的背包问题 特点是每个物品只有一件供你选择放还是不放
对于这个问题一般有两种解法 下面分别来介绍一下
① 二维解法
设f[i][j]表示前i件物品 总重量不超过j的最大价值 可得出状态转移方程
f[i][j]=max{f[i-1][j-a[i]]+b[i],f[i-1][j]}
代码如下
#include<iostream> using namespace std; int main() { int m,n; cin>>n>>m; int a[50001],b[50001]; int f[5001][5001]; for(int i=1;i<=n;i++)cin>>a[i]>>b[i]; for(int i=1;i<=n;i++) for(int j=m;j>0;j--){ if(a[i]<=j)f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]); else f[i][j]=f[i-1][j]; } cout<<f[n][m]<<endl; //最优解 //COYG }讯享网
②一维解法
设f[j]表示重量不超过j公斤的最大价值 可得出状态转移方程
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/29894.html