poj1837

基本背包,状态转移方程:

poj1837


#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;
	}
}


poj1837

上一篇:16、I/O流


下一篇:转:12款很棒的浏览器兼容性测试工具推荐