01背包 完全背包 算法解析

for (int i = 1; i <= n; i++) {
	for (int j = 0; j <= c; j++) {
		d[i][j] = (i == 1 ? 0 : d[i - 1][j]);
		if (j >= W[i])
				d[i][j] = max(d[i][j], d[i - 1][j - W[i]] + V[i]);
	}
}

3 5
2 3
3 5
4 7

for (int i = 1; i <= n; i++) {
	for (int j = 0; j <= c; j++) {
		d[i][j] = (i == 1 ? 0 : d[i - 1][j]);
		if (j >= W[i]) {
			d[i][j] = max(d[i][j], d[i - 1][j - W[i]] + V[i]);
			cout << "更改d" << j << " 使用" << j - W[i] << endl;
		}
	}
	cout << endl;
}

for (int i = 1; i <= n; i++) {
	for (int j = c; j >= 0; j--) {
		d[i][j] = (i == 1 ? 0 : d[i - 1][j]);
		if (j >= W[i]) {
			d[i][j] = max(d[i][j], d[i - 1][j - W[i]] + V[i]);
			cout << "更改" << j << " 使用" << j - W[i] << endl;
		}
	}
	cout << endl;
}

for (int i = 1; i <= n; i++) {
	for (int j = c; j >= 0; j--) {
		if (j >= W[i])
			d[j] = max(d[j], d[j - W[i]] + V[i]);
	}
}

for (int i = 1; i <= n; i++) {
	for (int j = c; j >= 0; j--) {
		d[i][j] = (i == 1 ? 0 : d[i - 1][j]);
		for (int k = 0; k * W[i] <= j; k++) {
			d[i][j] = max(d[i][j], d[i - 1][j - k * W[i]] + k * V[i]);
		}
	}
}

for (int i = 1; i <= n; i++) {
	for (int j = W[i]; j <= c; j++) {
		d[j] = max(d[j], d[j - W[i]] + V[i]);
	}
}