有n个集装箱要装上载重量为w的轮船，其中集装箱i的重量为wi。不考虑集装箱体积的限制，现在要将若干集装箱装上轮船，使他们的总重量为w，如果总重量相同要尽可能的使用少的集装箱。
有n个集装箱要装上载重量为C1、C2的轮船，其中集装箱i的重量为wi。问两艘轮船能否装下所有集装箱。
深搜所有情况，重点是要剪枝。
题目一剪枝条件是，tw + w[i] <= weight && tw + rw >= weight。当前集装箱装入后是否超过最大载重量，当前集装箱总重加上剩下集装箱总重是否大于最大载重。
题目二剪枝条件是，tw + w[i] <= c1 && tw + rw > maxW当前集装箱装入后是否超过最大载重量，当前集装箱总重加上剩下集装箱总重是否大于最大载重。
#include<iostream> #include<vector> using namespace std; vector <int> x(5,0); vector <int> op(5, 0); int min = 1e9; int w[] = { 0,10,40,40 }; int weight = 10; void dfs(int num, vector <int> &op, int tw, int rw,int count) { if (tw == weight&&count<::min) { for (int i = 0; i < 5;i++) { x[i] = op[i]; } ::min = count; //一开始我担心op[i]会存储上次的结果，但是发现没有。因为每次dfs结束，当前结点都置零了。 } else { for (int i = num; i < 5; i++) { if (tw + w[i] <= weight && tw + rw >= weight) {//主要就是剪枝做好就行了 op[i] = 1; dfs(num + 1, op, tw + w[i], rw - w[i], count + 1); op[i] = 0;//回溯放在这个位置，一定要贴近递归，贴近原则！！！ } //op[i] = 0;放在这个位置不对！！！会导致有些情况回溯不了 } } } int maxW = -1e9; int c1 = 50; int c2 = 50; void dfs2(int num, vector <int>& op, int tw, int rw) { if (num>0&&tw <= c1 && tw > maxW) { for (int i = 0; i < 5; i++) { x[i] = op[i]; } maxW = tw; } else { for (int i = num; i < 4; i++) { if (tw + w[i] <= c1 && tw + rw > maxW) {//主要就是剪枝做好就行了 op[i] = 1; dfs2(num + 1, op, tw + w[i], rw - w[i]); op[i] = 0;//回溯放在这个位置，一定要贴近递归，贴近原则！！！ } //op[i] = 0;放在这个位置不对！！！会导致有些情况回溯不了 } } } int main() { dfs2(0, op, 0, 90); for (auto it : x) { cout << it << " "; } }
