动态规划

找状态转移方程。

今日题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 105;

ll dp[N * N];

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int m, n;
	cin >> m >> n;
	for(int i=1;i<=n;++i) {//物品数量
		int s, w, v;//对于每种物品而言
		cin >> s >> w >> v;
		while(s--) {
			for(int j = m;j>=v;--j) {
				dp[j]=max(dp[j],dp[j-v]+w);
			}
		}
	}
	cout << dp[m] << '\n';
	return 0;
}

多重背包的二进制优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2005;

ll dp[N];
//核心：找到一种合并方式使得0-s中每个数都可被表示。
//之前是依次递增的，现在按照二进制打包。

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll m, n;
	cin >> m >> n;
	for(int i=1; i<=n; ++i) {
		ll s, w, v;
		cin >> s >> w >> v;

		vector<ll> vec;//存储打包的值1248等
		ll x = 1;
		while(s >= x) {
			vec.push_back(x);
			s -= x;
			x <<= 1;
		}
		if(s)vec.push_back(s);
		for(auto &k : vec) {
			for(int j = m; j >= k * v; --j) {
				dp[j] = max(dp[j], dp[j - k * v] + k * w);
			}
		}
	}
	cout << dp[m] << '\n';
	return 0;
}