差分约束，求最大值跑最短路，求最小值跑最长路，
最长路 xi-xj>=k添加j到i的权值为k的边
最短路xi-xj<=k添加j到i的权值为k的边
超级源点，到所有的点权值为0
注意用spfa跑时还要注意是否有负环
背包问题：
01背包
1 int w[N], v[N]; 2 int f[N]; 3 int main() { 4 int n, m; 5 cin >> n >> m; 6 for (int i = 1; i <= n; ++i) 7 cin >> w[i] >> v[i]; 8 for (int i = 1; i <= n; ++i) { 9 for (int j = m; j >= v[i]; --j)//从大往小表示单选 10 f[j] = max(f[j], f[j - v[i]] + w[i]); 11 } 12 cout << f[m] << endl; 13 return 0; 14 }
完全背包
int w[N], v[N]; int f[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i]; for (int i = 1; i <= n; ++i) { for (int j = v[i]; j >= m; ++j)//从小往大表示多选 f[j] = max(f[j], f[j - v[i]] + w[i]); } cout << f[m] << endl; return 0; }
多重背包
将他变成多个01背包问题求解就行
