- 1、二维费用背包问题(01)
- 2、潜水员(二维费用01)
- 3、数字组合(01 求方案数)
- 4、庆功会(多重背包应用 )
- 5、买书(完全背包求方案数)
#include2、潜水员(二维费用01)using namespace std; const int N = 110; int n, V, M; int f[N][N]; int main() { cin >> n >> V >> M; for (int i = 0; i < n; i ++ ) { int v, m, w; cin >> v >> m >> w; for (int j = V; j >= v; j -- ) for (int k = M; k >= m; k -- ) f[j][k] = max(f[j][k], f[j - v][k - m] + w); } cout << f[V][M] << endl; return 0; }
#include#include using namespace std; const int N = 22, M = 80; int n, m, K; int f[N][M]; int main() { cin >> n >> m >> K; memset(f, 0x3f, sizeof f); f[0][0] = 0; while (K -- ) { int v1, v2, w; cin >> v1 >> v2 >> w; for (int i = n; i >= 0; i -- ) for (int j = m; j >= 0; j -- ) f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w); } cout << f[n][m] << endl; return 0; }
#include#include using namespace std; const int N = 10010; int n, m; int f[N]; int main() { cin >> n >> m; f[0] = 1; for (int i = 0; i < n; i ++ ) { int v; cin >> v; for (int j = m; j >= v; j -- ) //f[j]不包含i ,f[j-v] 包含i f[j] += f[j - v]; } cout << f[m] << endl; return 0; }
#include5、买书(完全背包求方案数)using namespace std; const int N = 6010; int n, m; int f[N]; int main() { cin >> n >> m; for (int i = 0; i < n; i ++ ) { int v, w, s; cin >> v >> w >> s; for (int j = m; j >= 0; j -- ) for (int k = 0; k <= s && k * v <= j; k ++ ) f[j] = max(f[j], f[j - k * v] + k * w); } cout << f[m] << endl; return 0; }
#includeusing namespace std; const int N = 1010; int n; int v[4] = {10, 20, 50, 100}; int f[N]; int main() { cin >> n; f[0] = 1; for (int i = 0; i < 4; i ++ ) for (int j = v[i]; j <= n; j ++ ) f[j] += f[j - v[i]]; cout << f[n] << endl; return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)