怎么建设宣传网站,nas 做网站,自定义wordpress的实用技巧,上海网站建设报价方案一.前言若你想学习或正在学习动态规划#xff0c;背包问题一定是你需要了解的一种题型#xff0c;并且大多数人最初都是从背包问题入坑进而打开动态规划这一大门。背包问题分为多种#xff0c;你可以先掌握最常见的主要是三类#xff1a;01背包、完全背包、多重背包二.分析…一.前言若你想学习或正在学习动态规划背包问题一定是你需要了解的一种题型并且大多数人最初都是从背包问题入坑进而打开动态规划这一大门。背包问题分为多种你可以先掌握最常见的主要是三类01背包、完全背包、多重背包二.分析背包问题1)01背包在考虑一个物品时(从目标容器到物品大小容器考虑(保证只放一次))放入当前物品后所剩空间只能考虑其他物品★状态:考虑了前i个物品大小为j的容器能放入的最大价值的商品转移方程:f[i][j]max(f[i-1][j],f[i-1][j-V[i]])W[i])转移方程:dp[j]max(dp[j-V[i]],dp[j]])(注:等号右边的dp为上个循环的结果即考虑当前物品前面的所有物品的结果)2)多重背包在考虑一个物品时将放不同个数看成不同物品即可转化为01背包问题3)完全背包在考虑一个物品时(从物品大小容器到目标容器考虑(保证应放尽放))放入当前物品后所剩空间只能考虑其他物品三.例题1)题目01背包有 n 件物品和一个容量是 v 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi价值是 wi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。代码#include iostream
#include algorithm
using namespace std;
const int N 1010;
int v[N]; //每个物品的体积
int w[N]; //每个物品的价值
int f[N][N]; //状态转移方程上面有详细解释
int main(){int n,m;scanf(%d%d,n,m); //输入物品数量和背包容量for(int i 1;i n;i ) scanf(%d%d,v[i],w[i]); //输入每个物体的体积和价值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]) f[i][j] max(f[i][j],f[i - 1][j - v[i]] w[i]); //已经把f[i][j]赋值为f[i - 1][j]了现在就可以直接用f[i][j]了}}printf(%d,f[n][m]);return 0;
}2)题目有 n种物品和一个容量是v的背包每种物品都有无限件可用。第 i 种物品的体积是 vi价值是 wi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。代码#include iostreamusing namespace std;const int N 1100;
int n, m;
int v[N], w[N];
int f[N][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 1; j m; j ) {f[i][j] f[i - 1][j];for (int k 1; k j / v[i]; k ) {f[i][j] max(f[i][j], f[i - 1][j - k * v[i]] k * w[i]);}}}cout f[n][m] endl;return 0;
}3)题目有 n 种物品和一个容量是 v 的背包。第 i 种物品最多有 si 件每件体积是 vi价值是 wi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。代码#include iostream
#include algorithmusing namespace std;
const int N 110;int v[N], w[N], s[N];
int f[N][N];
int n, m;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 1; j m; j ){//枚举体积for(int k 0; k s[i]; k ){if(j k * v[i]){f[i][j] max(f[i][j], f[i - 1][j - k * v[i]] k * w[i]);}}}}cout f[n][m] endl;return 0;
} ~感谢观看❥(^_-)
