CooooldWind_の试炼历程 (6)

欢迎来到CooooldWind_的试炼历程

本系列主要是讲自己在平常做题的时候的一些小花絮，但是已经托更很久了，趁着刚搞好GitHub Pages，今天把之前的都推下（外传就算了吧）。

这里是P8742的题解

这一题是经典的“01背包”题，非常适合新手练手。

刚学完的来做做此题会有意想不到的效果。

思路

正如上面所述，这是能载入史册的经典的“01背包”题，适合刚入门的同学们做。

所以说，如何“01”呢？

二维数组“01”，第行第列表示能否为前个砝码中做出选或者不选的抉择，从而使选的砝码加起来重量为。

“01背包”的精髓还是关于状态转移方程 （以下简称状转）。那么本题的状转就是：

不放砝码，即上面的方案都能用。
只放现在的那个。
在对于第个砝码的选择中选择左边，即砝码重量加现在的天平上的重量等于原来的重量。
在对于第个砝码的选择中选择右边，即砝码重量减现在的天平上的重量等于原来的重量。

貌似很简单？对！就是这么简单（

放码！！

变量约定

int n,w[1451],w_max,ans;
bool dp[1451][114514];

这些是本题用到的变量，其中的含义如题，数组是存放砝码重量的。就是这些砝码加起来最大的重量。即是本题答案。

底下那个 dp 的二维数组是存状态的。

初始化

初始化 dp ：“dp[0][0] = 1; ”最好把这个都加上

别问我为什么，问就是血的教训（

真正的 DP ！！！

首先约定：

所有列的含义：第列指在前个砝码里面的所有的砝码排列（务必记住）。

为了防止你们看不懂我拿题目举例。

这个时候就可以给你们看代码了。

for(int i = 1;i <= n;i++){
	for(int j = 1;j <= w_max;j++){
		dp[i][j] = dp[i - 1][j];
		if(w[i] == j) dp[i][j] = 1;
		else if(dp[i - 1][j + w[i]] == 1) dp[i][j] = 1;
		else if(dp[i - 1][abs(j - w[i])] == 1) dp[i][j] = 1;
		if(dp[i][j] == 1 && i == n) ans++;
	}
}

双重循环，遍历dp。

第个砝码是否为，这是第一个 if 判断：“

的内容。

从前 $i$ 个砝码里面选择其中任意 $\{x|0≤x≤i\}$ 的重量能否组成 $j + w_i$ 或者 $|j- w_i|$ ，其实就是放左边放右边的问题，这是第二、三个if判断：
```cpp
else if(dp[i - 1][j + w[i]] == 1) dp[i][j] = 1;
else if(dp[i - 1][abs(j - w[i])] == 1) dp[i][j] = 1;

的内容。

第四个：“if(dp[i][j] == 1 && i == n) ans++; ”是特判，当判断最后一行时就可以算总数了。

我们可以把上面三个 if 组合一下，变成：

dp[i][j] = dp[i - 1][j] || w[i] == j || dp[i - 1][j + w[i]] || dp[i - 1][abs(j - w[i])];

本行代码等价于上面三个“if-else”结构，即满足任一条件即为 true。

全部代码

#include<bits/stdc++.h>
using namespace std;
int n,w[1451],w_max,ans;
bool dp[1451][114514];
int main(){
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> w[i];
		w_max = w_max + w[i];
	}
	dp[0][0] = 1;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= w_max;j++){
			dp[i][j] = dp[i - 1][j];
			if(w[i] == j) dp[i][j] = 1;
			else if(dp[i - 1][j + w[i]] == 1) 
            			dp[i][j] = 1;
			else if(dp[i - 1][abs(j - w[i])] == 1) 
            			dp[i][j] = 1;
			if(dp[n][j] == 1)
				ans++;
		}
	}
	cout << ans;
	return 0;
}

全部代码（压行

压行之后的难理解纯属烂活，建议新手看上面的。

#include<bits/stdc++.h>
int n,w[1451],w_max,ans,dp[1451][114514] = {1};
int main(){
    std::cin >> n;
    for(int i = 1;i <= n;i++) std::cin >> w[i];   
    for(int i = 1;i <= n;i++) w_max = w_max + w[i];
    for(int i = 1;i <= n;i++) for(int j = 1;j <= w_max;j++) dp[i][j] = dp[i - 1][j] || w[i] == j || dp[i - 1][j + w[i]] || dp[i - 1][abs(j - w[i])];
    for(int j = 1;j <= w_max;j++) if(dp[n][j] == 1) ans++;
    std::cout << ans;
}

注意：这个压行代码洛谷跑了会CE，但是本地跑没问题。慎用。

后话

不少人喜欢抄题解我是知道的，但是把所有代码放出来的意义，我认为是为了方便大家理解代码中的逻辑，所以我的代码风格统一，方便阅读。

希望大家不要抄题解，理解并自己手写一遍是最高效的方案；也希望能通过这个例子了解01背包的出题方式，并且灵活运用01背包dp去解题。

有用？点个赞再走吧

CooooldWind_的小站