动态规划
动态规划
只有多练才能积累，之后就变练变总结，不要写云里雾里的东西了。
背包问题
背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。一般来讲，背包问题有以下几种分类：
-
01背包问题
-
完全背包问题
-
多重背包问题
01背包问题
动态规划重点的是状态转移方程:01背包，代表着物品只有两种可能性 - 放和不放
f[i][j]中的前i件物品放入容量为j的背包中。我们很容易可以看出，数组的第一个维度我们存储的是物品的不同种类，第二个维度存储的是我们的背包容量。
可以这样理解，
f[i][j]就是i物品放入背包容量为j的状态
更新容量我们就使用：max(f[i-1][j-w[i]]+c[i],f[i-1][j])
当然放入物品的时候有两种情况，我们分别判断一下：
第一种，不放入我们的物品。f[i][j] = f[i-1][j]:这里很好理解，遍历到i-1这个物品，放入不下j就不变化 , 状态不更新把状态传下去。
第二种，放入我们的物品。这里就要考虑代价，也就是f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+c[i]) , 放入物品减去对应的体积吗，更新对应的值。记住每一个位置表示着一个状态。
//模版思想研究//用二维数组来理解 for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) if(j<w[i]) //先决条件：这个位置放不了i这个物品了 f[i][j] = f[i-1][j]; else f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+c[i]); cout<<f[n][m];用二维数组来理解十分容易，但是会浪费一些容量。我们不妨使用滚动数组来构造背包问题。思路如下：
-
外层循环遍历每个物品
i。 -
内层循环遍历背包的容量
j。 -
如果当前物品的重量
w[i]大于背包的容量j，表示无法将物品i放入背包中，因此f[j]的值不变，即f[j] = f[j]。这对应于提到的不放入我们的i情况。
否则，如果w[i]小于或等于背包容量j，表示可以考虑将物品i
放入背包中。在这种情况下，需要比较两种情况：
f[j]表示不放入物品i时的最大价值（对应于提到的f[j] = f[j]情况）。
f[j-w[i]] + c[i]表示放入物品i后的最大价值，其中f[j-w[i]]是在剩余容量j-w[i]下的最大价值，而c[i]是物品i的价值。你需要选择这两种情况中的较大值作为f[j]的新值，即f[j] = max(f[j], f[j-w[i]] + c[i])。
//用j逆序排序 for(int i = 1;i<=n;i++) for(int j = m;j>=1;j--) if(j<w[i]) f[j] = f[j]; else f[j] = max(f[j],f[j-w[i]]+c[i]);
//模版#include <iostream>#include <cstring>using namespace std;
const int MAXN = 1005;
int N, V; // N表示物品个数，V表示背包容量int w[MAXN], v[MAXN]; // w[i]表示第i个物品的重量，v[i]表示第i个物品的价值int dp[MAXN]; // dp[i]表示容量为i的背包所能装下的最大价值
int main() { cin >> N >> V; for (int i = 1; i <= N; i++) { cin >> w[i] >> v[i]; }
memset(dp, 0, sizeof(dp)); // 初始化dp数组 for (int i = 1; i <= N; i++) { for (int j = V; j >= w[i]; j--) { // 从后往前遍历，避免重复选择物品 dp[j] = max(dp[j], dp[j - w[i]] + v[i]); // 状态转移方程 } }
cout << dp[V] << endl; // 输出结果
return 0;}完全背包问题*
完全背包问题，就是01背包的变形，每个物品可以无限次放入。f[i][j]依然和01背包问题相同的，i表示的是我们物品的种类，j表示的是我们背包的容量。放入物品的时候，我们需要选择放入这个物品我们的价值是否会增加
过程:
背包容量放不下我们当前这个物品 条件就是j<w[i] 所以说我们的容量还是不变f[i][j] = f[i-1][j]; (这也就解释了我们可以使用一维数组来维护我们的背包)，这里的i-1表示的是前一个物品，就是我们不会改变当前的背包状态
-
当背包可以放入我们当前这个物品，条件也就是
j>=w[i]我们有两种选择 - 放入和不放入。放入的话就是f[i][j] = f[i][j-w[i]]+c[i] -
c[i]是我们的价值(这里的i的意思就是我们物品是无穷的，每一个i表示的意思就是取出当前i这个物品的其中一个) 不放入就是f[i][j] = f[i-1][j]j就不会变化 -
我们最终的转移方程就是 上面两个合并的结果
f[i][j] = f[i-1][j] (j<w[i])f[i][j] = max(f[i-1][j],f[i][j-w[i]]+c[i])
下面是代码模版：
for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) //这里m是容量 { if(j<w[i]) f[i][j] = f[i-1][j]; else f[i][j] = max(f[i-1][j],f[i][j-w[i]]+c[i]); //c[i]是i物品的价值 }printf("%d",f[n][m]);
#include <iostream>#include <vector>using namespace std;
// 完全背包问题的动态规划解法int knapsack(int W, vector<int>& wt, vector<int>& val) { int n = wt.size(); vector<int> dp(W + 1, 0);
for (int i = 1; i <= n; i++) { for (int j = wt[i-1]; j <= W; j++) { dp[j] = max(dp[j], dp[j - wt[i-1]] + val[i-1]); } }
return dp[W];}
// 测试int main() { vector<int> wt = {2, 3, 4, 5}; vector<int> val = {3, 4, 5, 6}; int W = 8; cout << "最大价值为：" << knapsack(W, wt, val) << endl; return 0;}多重背包问题
在01背包的基础之上，让每一种物品都有对应的容量。只需要多加一个枚举数量的变量就行。
需要注意的是，for循环枚举的是位置，而不是值。
//在01背包的基础上，让每一件物品都有他们的数量 //1.v[i],w[i] 体积和价值 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]); //2.v[i],w[i],s[i]; 体积 价值 数量 for(int i = 1;i<=n;i++) for(int j = m;j>=v[i];j--) for(int k = 0;k<=s[i]&&k*v[i]<=j;k++) //这里的k表示的是选择物品的数量 - s[i]表示的是当前位置的i物品的数量 f[j] = max(f[j],f[j-k*v[i]]+k*w[i]);//朴素做法const int N = 1e5+10;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]; //这里就是输入对应的价值，由i下标规定数据 for(int i = 1;j<=n;j++) for(int j = 0;j<=m;j++) for(int k = 0;k<=s[i]&&k*v[i]<=j;k++) f[i][j] = max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k); //这里i-1是把这个i物品选择了（选够了就剔除） - 只要找到一个符合的k就行（我们不管怎么实现的就行） cout<<f[n][m]<<endl; return 0;
}
int num = 1;//拆分计数for(int i = 1;i<=n;i++){ //v,w,s; 体积，价值，数量 cin>>v>>w>>s; for(int j = 1;j<=s;j<<=1){ //<<=是左移位赋值运算符,等价*2 vv[num] = j*v; //存体积 ww[num++] = j*w; //存价值 s-=j; } if(s){ //体积和价值拆分 - 封装为新的数组 vv[num] = s*v; ww[num++] = s*w; }}
//01背包问题 - 基础 for(i = 1;i<num;i++) for(j = m;j>=vv[i];j--) f[j] = max(f[j],f[j-vv[i]]+ww[i]);cout<<f[m];#include <iostream>#include <cstring>using namespace std;
const int MAXN = 1005; // 物品的最大数量const int MAXV = 100005; // 背包的最大容量int n, V; // 物品的数量和背包的容量int w[MAXN], v[MAXN], s[MAXN]; // 分别表示物品的重量、价值和数量int dp[MAXV]; // dp[i]表示容量为i的情况下，可以获得的最大价值
// 二进制优化void binary_optimization(int x, int y) { for (int j = V; j >= x; j--) { for (int k = 0; k <= s[y] && k * x <= j; k++) { dp[j] = max(dp[j], dp[j - k * x] + k * y); } }}
int main() { cin >> n >> V; for (int i = 1; i <= n; i++) { cin >> w[i] >> v[i] >> s[i]; }
for (int i = 1; i <= n; i++) { for (int j = 1; j <= s[i]; j *= 2) { binary_optimization(w[i] * j, v[i] * j); // 调用二进制优化函数 s[i] -= j; } if (s[i] > 0) { binary_optimization(w[i] * s[i], v[i] * s[i]); } }
cout << dp[V] << endl; // 输出答案 return 0;}//二进制优化#include <iostream>#include <algorithm>
using namespace std;
const int N = 12010, M = 2010;
int n, m;int v[N], w[N];int f[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 ++ ; //这里是二进制优化的核心 - 就是将s拆成2进制 //核心是将物品拆分为2的幂次方个物品 //每次都拿s拆开二进制的数量 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 -- ) f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;}分组背包问题
在01背包的基础上，增加了物品序列号。只需要将价值生成一个组的序列号就行，然后照常枚举出我们需要的值。
//朴素做法for(int i = 1;i<=n;i++) for(int j = 1;j<=V;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]); //不选取i 选取i }cout<<f[n][V];
//分组朴素做法for(int i = 1;i<=n;i++) for(int j = 1;j<=V;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][V];
应该也可以用二进制优化策略
#include <iostream>#include <algorithm>
using namespace std;
const int N = 12010, M = 2010;
int n, m;int v[N], w[N];int f[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; //这里是将s数量分二进制 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;
//2.这里就是选择最大 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] << endl;
return 0;}