基本背包,状态转移方程:
#include <iostream> using namespace std; int dp[21][15005]; int main() { int c, g, i, j, k; while (cin >> c >> g) { int c1[25], w[25]; for (i = 0; i < c; i++) { cin >> c1[i]; } for (i = 0; i < g; i++) { cin >> w[i]; } memset(dp, 0, sizeof(dp)); dp[0][7503] = 1; for (i = 1; i <= g; i++) { for (j = 0; j < 15005; j++) { if (dp[i - 1][j]) { for (k = 0; k < c; k++) { dp[i][j + w[i - 1] * c1[k]] += dp[i - 1][j]; } } } } cout << dp[g][7503] << endl; } }