1：子集和问题
给定n个不同的正整数集合w=（w1，w2，…，wn）和一个正数W，要求找出w的子集s，使该子集中所有元素的和为W。
输入格式:
第一行输入n和W，第二行依次输入n个数。
输出格式:
每行输出一个符合要求的子集。
输入样例1:
4 31 11 13 24 7
输出样例1:
11 13 7 24 7
#include<iostream> using namespace std; const int N = 1010; int n, m; int w[N], op[N]; void dfs(int idx, int sum) { if(sum > m || idx > n) return ; // 可行性减枝 if(sum == m) { for (int i = 0; i < n; i ++ ) if(op[i]) cout << w[i] << ' '; cout << endl; return ; } op[idx] = 1; dfs(idx + 1, sum + w[idx]); op[idx] = 0; dfs(idx + 1, sum); } int main() { cin >> n >> m; for (int i = 0; i < n; i ++ ) cin >> w[i]; dfs(0, 0); return 0; }
2：0/1背包问题
0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求而且重量和恰好为W具有最大的价值。
输入格式:
第一行输入背包载重量W及背包个数n，再依次输入n行，每行为背包重量wi和价值vi。
输出格式:
第一行输出装入背包内的物体编号(末尾有空格),若没有任何物品能装入，输出: No，第二行输出背包内的物体总价值。
输入样例1:
5 10 2 6 2 3 6 5 5 4 4 6
输出样例1:
1 2 5 15
输入样例2:
2 10 11 2 13 100
输出样例2:
No 0
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int n, m; int v[N], w[N], op[N], f[N]; int maxv; // 下标，当前体积，当前价值，标记 void dfs(int idx, int cv, int cw, int op[N]) { if(idx > n ) { if(maxv < cw) { maxv = cw; for (int i = 1; i <= n; i ++ ) f[i] = op[i]; } return; } op[idx] = 0; dfs(idx + 1, cv, cw, op); if(cv + v[idx] <= m) // 剪枝 { op[idx] = 1; dfs(idx + 1, cv + v[idx], cw + w[idx], op); } } int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; dfs(1, 0, 0, op); int tt = 0; for (int i = 1; i <= n; i ++ ) { if(f[i]) { tt = 1; cout << i << ' '; } } if(!tt) cout << "No"; cout << endl << maxv; return 0; }
3：求解简单装载问题
有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi。不考虑集装箱的体积限制，现要这些集装箱中选出若干装上轮船，使它们的重量之和等于W，当总重量相同时要求选取的集装箱个数尽可能少。
输入格式:
第一行输入集装箱个数n和载重量W，第二行依次输入n个集装箱的重量wi。
输出格式:
输出选取的集装箱编号（按输入顺序从1开始依次编号）。
输入样例1:
5 10 5 2 6 4 3
输出样例1:
3 4
#include <iostream> using namespace std; const int N = 1010; int n, m; int w[N], op[N], f[N]; int minv = 0x3f; void dfs(int u, int cw, int sw, int op[], int cnt) { if(u > n) { if(cw == m && cnt < minv) { minv = cnt; for (int i = 1; i <= n; i ++ ) f[i] = op[i]; } return ; } op[u] = 1; if(cw + w[u] <= m) //左孩子结点剪枝：装载满足条件的集装箱 dfs(u + 1, cw + w[u], sw - w[u], op, cnt + 1); op[u] = 0; if(cw + sw - w[u] >= m) //右孩子结点剪枝 dfs(u + 1, cw, sw - w[u], op, cnt); } void Print() { for (int i = 1; i <= n; i ++ ) if(f[i]) cout << i << ' '; } int main() { cin >> n >> m; int sw = 0; for (int i = 1; i <= n; i ++ ) { cin >> w[i]; sw += w[i]; } dfs(0, 0, sw, op, 1); Print(); return 0; }
