01背包

  • n件物品,每件重量w[i], 价值c[i], 选若干件放进容量为V的背包,使背包里面价值最大

动态规划

$f[i][j]​$ 表示前i件物品放进容量为j的背包的总价值

$f[i][j]=max(f[i-1][j], f[i-1][j-w[i]]+c[i])$

复杂度$O(N\times V)$

DFS解法

  • 这是指数型枚举,选或不选问题。变化的参数是sumC, sumW
  • 表示前面0到i-1件的总重量和总价值
  • 外面记录的参数是maxValue!!!!!!注意不要忘记这个参数!!!!
  • 复杂度$O(2^N)​$
1
2
3
4
5
6
7
8
9
10
void dfs(int i, int sumC, int sumW){
if(i == n){
if(sumW <= V && sumC > maxValue){
maxValue = sumC;
}
return;
}
dfs(i+1, sumC, sumW); //不选i
dfs(i+1, sumC + c[i], sumW + w[i]); //选i
}

剪枝!!!不用在最后判断!!如果中间发现已经超了就return!!!!注意此时更新maxValue不能等到最后了!必须在中间进行。

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int i, int sumC, int sumW){
if(i == n){ //已经完成选择
return;
}
dfs(i+1, sumC, sumW);
if(sumW + w[i] <= V){
if(sumC + c[i] > maxValue){
maxValue = sumC + c[i];
}
dfs(i+1, sumC + c[i], sumW + w[i]);
}
}

枚举子序列

  • 指数型枚举的另一个例子:寻找一个序列的所有子序列
    • 等价于给n个数选若干个,输出所有方案
  • 组合型枚举:从n个数中选k个,使之和为x,若有多个,输出平方和最大的那个
    • 组合型枚举相比指数型枚举多了一个剪枝条件,边界条件还要变!关键还是看题!!!
    • 这里我们还要思考在每个状态要携带的参数!!!!!!!!
      • 当前状态有哪些参数!!
      • 比如:当前的序列的和!!!当前序列的平方和!!!!
      • 还要保存一个临时方案和最优方案vector,以及这个最优方案的平方和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> temp, ans;
int ans_sum = -1; //注意!
int k, n, x;
int a[maxn];
void dfs(int i, int now_k, int sum, int sq_sum){
if(now_k == k && sum == x){ //已经选了k个数,now_k初始值是0
if(ans_sum < sq_sum){
ans_sum = sq_sum;
ans = temp;
}
return;
}
if(i == n || sum > x || now_k > k){
return;
}
//选i
temp.push_back(a[i]);
dfs(i+1, now_k+1, sum+a[i], sq_sum+a[i]*a[i]);
temp.pop_back(); //恢复现场,进入不选i的分支,这样其实更好理解一些!
dfs(i+1, now_k, sum, sq_sum); //不选i
}

重新思考这道题:

  • 组合型枚举
  • 每个状态的参数:当前枚举到i项,当前的sum,当前序列平方和,当前已经选了多少项(因为是组合型枚举)
  • 全局变量:最优序列,最优序列的平方和,当前序列
  • 边界条件:已经选了k个,并且和为x
  • 剪枝:递归到n或者和大于x或者当前选的项数超过了k
  • 先写选i的分支:push_back,dfs,pop_back;注意不要忘记pop_back
  • 再写不选i的分支

更改:每个整数可以被选择多次,也是选k个数,和为x

  • 继续选i的分支:dfs(i, now_k+1, sum+a[i], sq_sum+a[i] * a[i]);
  • 直到某一时刻不选i,进入不选i的分支:dfs(i+1, now_k, sum+a[i], sum+a[i]* a[i]);
  • 这道题又变成了完全背包了貌似??