白书例题

2.3.1 01背包问题-搜索解法

我的程序……还有问题木有改出来

#include <iostream> #include <algorithm> using namespace std; /**这是我的垃圾程序**/ /*n个重量和价值分别为wi vi的物品，从这些物品中挑选出总重量不超过W的物品， 求所有挑选方案中价值总和的最大值 1 <= n <= 100 1 <= wi,vi <= 100 1 <= W <= 10000*/ //int n, w, maxv; int n, w; int weight[101] = {0}, value[101] = {0}; /***蓝桥杯的那个走迷宫拿宝藏是不是也是背包问题？***/ int dfs(int nownumber, int resweight) //nownumber标记走到数组的第几个 nowweight标记当前的总重量 //change: nownumber标记走到数组的第几个 resweight标记剩余可用的重量额度 { int maxv;/**为什么要在这里int maxv 每次递归都重新初始化？**/ if(nownumber == n) //已经走到数组尽头 //事实上作为递归 是在这里才开始真正maxv相加 而不能理解为maxv=0直接return 0 { maxv = 0; } //并不超过总重量 if(weight[nownumber] <= resweight) { maxv = max(dfs(nownumber + 1, resweight - weight[nownumber]) + value[nownumber], dfs(nownumber + 1, resweight)); //注意这里如果写选择拿的情况要加上value[now]! } else // 超过总重量 只能选择不拿 { maxv = dfs(nownumber + 1, resweight); } return maxv; } int main() { /*4 5 **2 1 3 2 weight **3 2 4 2 value */ cin >> n >> w; for(int i = 0;i < n;i++) cin >> weight[i]; for(int i = 0;i < n;i++) cin >> value[i]; int ans = dfs(0, w); //最开始写的是dfs(0,0) 一边是当前数组序号 一边是目前的总重量 cout << ans; return 0; }

标程

#include <iostream> #define MAX_N 10001 /***我是标程***/ using namespace std; int n, W; int w[MAX_N] = {0}, v[MAX_N] = {0}; int rec(int i, int j) { int res; if(i == n) { res = 0; //已经没有剩余物品 cout << "i = " << i << endl; cout << "i == n res = " << res << endl; cout << endl; /**要注意这里不是return res(res = 0) 而是从递归的深处一层层回调**/ } else if(j < w[i]) { //无法挑选这个物品 res = rec(i + 1, j); cout << "i = " << i << endl; cout << "j < w[i] - " << rec(i + 1, j) << endl; //已经调用过rec() 还能再次调用吗 cout << endl; } else { //挑选和不挑选都进行尝试 res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]); /**最初rec(0, W) 会来到这里 但是这是递归！不是循环 ***递归我们设置的i == n 的终止条件不是通过循环变量i++实现 ***而是通过一层层递归调用，在rec( , )里i++直到i == n 触发终止条件 ***再一层层返回**/ cout << "i = " << i << endl; cout << "将挑选不挑选均进行尝试" << endl; cout << "不挑选 - " << rec(i + 1, j) << endl; cout << "挑选 - " << rec(i + 1, j - w[i]) + v[i] << endl; cout << endl; } return res; } int main() { /*4 5 **2 3 1 2 3 4 2 2*/ cin >> n >> W; for(int i = 0;i < n;i++) { cin >> w[i] >> v[i]; } cout << rec(0, W); return 0; }

这个问题最主要的是，发现自己对递归的理解和掌握还很欠缺。对递归解决问题的整个过程还有理解上的不足。

2.3.1 01背包问题-递推解法

#include <iostream> #define MAX_N 10001 /***我是标程***/ using namespace std; int n, W; int w[MAX_N + 1] = {0}, v[MAX_N + 1] = {0}, dp[MAX_N + 1][MAX_N + 1] = {0}; /*n个重量和价值分别为wi vi的物品，从这些物品中挑选出总重量不超过W的物品， 求所有挑选方案中价值总和的最大值 1 <= n <= 100 1 <= wi,vi <= 100 1 <= W <= 10000*/ int main() { /*4 5 **2 3 1 2 3 4 2 2*/ cin >> n >> W; for(int i = 0;i < n;i++) { cin >> w[i] >> v[i]; } /*对于每一种状态 如果能拿起来，便判断max 如果不能，便=上一状态*/ //从第i个物品开始挑选总重小于j时物品的最大值 //用非递归的方式重写rec()函数 for(int i = n - 1;i >= 0;i--) { for(int j = 0;j <= W;j++)/****/ { if(w[i] > j)//当前物品重量w[i]大于剩余可使用重量额度 dp[i][j] = dp[i + 1][j]; else { //dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]); /**为什么是+而不是-： rec()里是从0→n 这一分支里是像深处递归，也就是i++ ***放在这里用循环写就相当于反向走（因为循环是n→0）**/ } } } cout << dp[0][W] << endl; return 0; }

2.3.1 最长公共子序列问题LCS（求长度）

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; int dp[1001][1001]; //dp[i][j] 子序列(a)第i位选b的可能性 int main() { /*给定两个字符串 求最长公共子序列的长度 **两串长度1-1000*/ string a, b; cin >> a >> b; int lena = a.length(), lenb = b.length(); memset(dp, 0, sizeof(dp)); /*int lena = a.length(), lenb = b.length(), cnt = 0; for(int i = 0;i < min(lena, lenb);i++) { if(a[i] == b[i]) cnt++; else break; }*/ /*这种想法是错误的，一位一位找下去找的是substring而非subsequence **并且这样找只是找到了从第一位开始的longest subsring而不是整个string的the longest*/ /**递推关系**/ /*dp[i][j] = 0 i,j = 0 ***********= dp[i-1][j-1]+1 a[i]=b[j] ***********= max{dp[i-1][j],dp[i][j-1]} a[i]!=b[j]*/ for(int i = 1;i <= lena;i++) { for(int j = 1;j <= lenb;j++) { if(a[i - 1] == b [j - 1]) //一开始写的是i j从0开始 但是会出现数组越界 { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]); } } } cout << dp[lena][lenb] << endl; return 0; }

第0位（i = 0,j =0)时dp[i][j]值为0，这里i j 的循环与实际字符串的下标存在差。dp[0][0]是为了给递推关系一个初值，而不是指的比较a[0]与b[0]。

HDU1159

要注意多组数据读入这里采用的读入方式。

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; int dp[1001][1001]; //dp[i][j] 子序列(a)第i位选b的可能性 char a[1010],b[1010]; int main() { /*给定两个字符串 求最长公共子序列的长度 **两串长度1-1000*/ //while(~scanf(" %s", a)) while(scanf(" %s", a) != EOF) { scanf(" %s", b); int lena = strlen(a), lenb = strlen(b); memset(dp, 0, sizeof(dp)); for(int i = 1;i <= lena;i++) { for(int j = 1;j <= lenb ;j++) { if(a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } printf("%d\n",dp[lena][lenb]); } return 0; }

2.3.1 最长公共子序列问题LCS（求路径）

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; int dp[1001][1001]; //dp[i][j] 子序列(a)第i位选b的可能性 char a[1010],b[1010],c[1010]; int main() { /*给定两个字符串 求最长公共子序列并输出 **两串长度1-1000*/ /*非多输入*/ scanf("%s", a); scanf("%s", b); int lena = strlen(a), lenb = strlen(b); memset(dp, 0, sizeof(dp)); for(int i = 1;i <= lena;i++) { for(int j = 1;j <= lenb ;j++) { if(a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } memset(c, 0, sizeof(c)); //即使全局变量自动初始化为0 也要养成随时初始化的好习惯 int lsc = dp[lena][lenb], i = lena, j = lenb, z = 0; while(i > 0 && j > 0) { if(a[i - 1] == b[j - 1]) { c[z++] = a[--i];/**注意这里不是a[i]*/ j--; } else if(dp[i - 1][j] > dp[i][j - 1]) i--; else j--; } for(int m = z - 1;m >= 0;m--) printf("%c", c[m]); /**注意是%c(char)不是%s*/ return 0; }

对LCS的应用

这道题一开始始终没读懂题意，题意其实是让你找两个串的lcs，之后任选一个串减去lcs，再把两个串拼到一起。

#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; int dp[1010][1010]; char a[1010], b[1010], c[1010], d[2010]; int lena, lenb; int main() { while(~scanf(" %s", a)) { memset(dp, 0, sizeof(dp)); scanf(" %s", b); lena = strlen(a); lenb = strlen(b); for(int i = 1;i <= lena;i++) { for(int j = 1;j <= lenb;j++) { if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } //求出lcs memset(c, 0, sizeof(c)); int cnti = lena, cntj = lenb, z = 0; while(dp[cnti][cntj]) { if(a[cnti-1] == b[cntj-1]) { c[z++] = a[--cnti]; cntj--; } else if(dp[cnti-1][cntj] > dp[cnti][cntj-1]) c[z++] = a[--cnti]; else c[z++] = b[--cntj]; } while(cnti != 0) c[z++] = a[--cnti]; while(cntj != 0) c[z++] = b[--cntj]; for(int x = z - 1; x >= 0; x--) printf("%c", c[x]); printf("\n"); } return 0; }

2.3.1 完全背包问题

#include <iostream> #include <cstdio> using namespace std; #define MAX_W 10000 #define MAX_N 100 /*有n种价值和重量分别为wi vi的物品。 从这些物品中挑选总重量不超过W的物品，求出挑选物品价值总和的最大值。 在这里，每种物品可以挑选任意多种*/ /*1 <= n <= 100 1 <= wi,vi <= 100 1 <= W <= 10000*/ int dp[MAX_N + 1][MAX_W + 1] = {0}, w[MAX_N] = {0}, v[MAX_W] = {0}; int main() { //dp[i][j] 第i件物品时剩余可用重量j int n, W; scanf("%d %d", &n, &W); for(int i = 0;i < n;i++) scanf("%d %d", &w[i], &v[i]); for(int i = 0;i < n;i++) { for(int j = 0;j <= W;j++) { if(w[i] > j) //拿不起 dp[i+1][j] = dp[i][j]; else dp[i+1][j] = max(dp[i][j], dp[i+1][j-w[i]]+v[i]); } } cout << dp[n][W]; return 0; }

一重循环

#include <iostream> #include <cstdio> using namespace std; #define MAX_N 100 #define MAX_W 10000 int v[MAX_N+1], w[MAX_N+1], dp[MAX_N+1]; int main() { int n = 0, W = 0; scanf("%d %d", &n, &W); for(int i = 0;i < n;i++) scanf("%d %d", &w[i], &v[i]); for(int i = 0;i < n;i++) { /**若为完全背包**/ //for(int j = w[i];j <= W;j++) for(int j = W;j >= w[i];j--) { dp[j] = max(dp[j], dp[j-w[i]]+v[i]); } } printf("%d", dp[W]); return 0; }

多重背包-多重部分和问题 HDU 1059

*PS.POJ 1276 Cash Machine原理一样 复杂度O(K(mi求和))的版本（TLE）

#include <iostream> #include <cstdio> using namespace std; #define MAX_N 20000 #define MAX_V 12000 int marble[7]; bool dp[MAX_N + 1][MAX_V + 1]; int main() { int cnt = 0; while(scanf("%d %d %d %d %d %d", &marble[0], &marble[1], &marble[2], &marble[3], &marble[4], &marble[5])) { int total = 0, flag = 0; for(int i = 0;i < 6;i++) { if(marble[i] != 0) { total += marble[i] * (i + 1); flag = 1; } } if(flag) { cnt++; if(total % 2 != 0) printf("Collection #%d:\n Can't be divided.\n", cnt); else { int K = total / 2; dp[0][0] = true; for(int i = 0;i < 6;i++) { for(int j = 0;j <= K;j++) { for(int z = 0;z <= marble[i] && z * (i + 1) <= j;z++) { dp[i + 1][j] |= dp[i][j - z*(i+1)]; } } } if(dp[6][K]) printf("Collection #%d:\n Can be divided.\n", cnt); else printf("Collection #%d:\n Can't be divided.\n", cnt); } } else { break; } } return 0; }

利用一维数组 复杂度O(nK)的版本（TLE)

#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> using namespace std; #define MAX_V 12000 int marble[7] = {0}, dp[MAX_V + 1]; //dp[i][j] 前i种数加和为j时第i种剩下几个 int main() { int cnt = 0; while(scanf("%d %d %d %d %d %d", &marble[1], &marble[2], &marble[3], &marble[4], &marble[5], &marble[6])) { int sum = 0, flag = 0; if(marble[1]+marble[2]+marble[3]+marble[4]+marble[5]+marble[6] == 0) flag = 0; else flag = 1; sum = marble[1]+marble[2]*2+marble[3]*3+marble[4]*4+marble[5]*5+marble[6]*6; if(flag) { cnt++; if(sum % 2 != 0) printf("Collection #%d:\n Can't be divided.\n", cnt); else { int K = sum / 2; memset(dp, -1, sizeof(dp)); dp[0] = 0; for(int i = 1;i <= 6;i++) { for(int j = 0;j <= K;j++) { if(dp[j] >= 0) { dp[j] = marble[i]; } else if(j < i || dp[j - i] <= 0) { dp[j] = -1; } else dp[j] = dp[j - i] - 1; } } if(dp[K]) printf("Collection #%d:\n Can be divided.\n", cnt); else printf("Collection #%d:\n Can't be divided.\n", cnt); } } else { break; } } return 0; }

利用二进制性质优化版本。 离奇的是我在Can\Can’t be divided.后面\n就Presentation Error. 但是如果把\n挪到单独的printf里面就可以AC。搞不太懂……

#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define MAX_N 210005 //最多20000件 int marblenum[7], marblevalue[7]={0,1,2,3,4,5,6}, dp[MAX_N+1], a[200]; int main() { int testnum = 0; while(scanf("%d%d%d%d%d%d",&marblenum[1],&marblenum[2],&marblenum[3],&marblenum[4],&marblenum[5],&marblenum[6])) { int flag = 0, sum = 0; for(int i = 1;i < 7;i++) { if(marblenum[i]!=0) { flag = 1; sum += marblenum[i] * i; } } if(flag) { testnum++; if(sum % 2 != 0) { printf("Collection #%d:\nCan't be divided.",testnum); } else //可以整除的情况 { int contain = sum / 2,cnt = 0; for(int i = 1;i <= 6;i++)//遍历每一种 { //按规律分堆 for(int j = 1;j <= marblenum[i];j *= 2)//n+1>2^k 2^j <= n 相当于 2^j < n+1 { a[++cnt] = i*j; //生成的这一堆的价值 marblenum[i] -= j; //用掉多少就减去多少 } if(marblenum[i] != 0) //没有完全用光 a[++cnt] = i*marblenum[i]; //额外放一堆 } memset(dp, 0, sizeof(dp)); //此时转化为01背包 已经拥有cnt种物品 每件一个 最大容量contain for(int i = 1;i <= cnt;i++) { for(int j = contain;j >= a[i];j--) { dp[j] = max(dp[j],dp[j-a[i]]+a[i]); } } if(dp[contain]!=contain) { printf("Collection #%d:\nCan't be divided.", testnum); } else { printf("Collection #%d:\nCan be divided.", testnum); } } printf("\n\n"); } else //全部为0 结束输入 { break; } } return 0; }

最长上升子序列问题LIS

O(n^2)

#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> using namespace std; #define MAX_N 1000 typedef long long ll; int dp[MAX_N + 1];//以ai为末尾的LIS长度 ll num[MAX_N + 1]; int main() { int n = 0; scanf("%d", &n); for(int i = 1;i <= n;i++) //c读入longlong 用%lld scanf("%lld", &num[i]); int res = 0; for(int i = 1;i <= n;i++) { dp[i] = 1; //自己 长度为1 for(int j = 1;j < i;j++) { if(num[j] < num[i]) dp[i] = max(dp[i], dp[j]+1); } res = max(res, dp[i]); } printf("%d \n", res); return 0; }

O(nlogn)

#include <iostream> #include <cstdio> using namespace std; #define MAX_N 1000 #define INF 100000 int origin[MAX_N + 10], dp[MAX_N + 10];//dp[i] 长度为i+1的LIS中末尾元素最小值 int main() { int n = 0; scanf("%d", &n); for(int i = 1;i <= n;i++) { scanf("%d", &origin[i]); } fill(dp, dp+n+1, INF);//INF初始化 //如果不存在i长度的lis dp[i] = INF //O(n^2) /*dp[0] = 0; for(int i = 1;i <= n;i++) {//找长度为i的min if(dp[i-1] != INF) //此前存在 { for(int j = i;j <= N;j++)// { if(origin[j] > dp[i-1]) dp[i] = min(dp[i], origin[j]); } } else dp[i] = INF; } for(int i = n-1;i >= 0;i--) { if(dp[i+1] != INF) { printf("%d\n", i+1); break; } }*/ //binary search O(nlogn) for(int i = 0;i < n;i++) { *lower_bound(dp, dp+n, origin[i]) = origin[i]; } printf("%d\n", lower_bound(dp, dp+n, INF)-dp); return 0; }

2.3.3 有关计数问题的dp-划分数

2.3.3 多重集组合数

dp刷题记录