0 1背包问题

除去h的条件

1.状态方程的确认：由0 1背包问题不难确认状态方程f[i][j] 其含义为从下标为[0-i]的物品里任意取，放进容量为j的背包，威力总和最大是多少。
2.状态的转移：
	1.不拿i:此时f[i][j] = f[i - 1][j]
	2.拿i:此时f[i][j] = f[i - 1][j - w[i]] + v[i],其中f[i - 1][j - w[i]] 为背包容量为j - w[i]时不放物品i的最大威力。
3.总结相关代码：

for（int i = 0;i <= n;i++）{//从物品遍历
	for(int j = 0;j <= m;j++){
    	f[i][j] = f[i - 1][j];
        if(j >= w[i]) f[i][j] = max(f[i][j],f[i - 1][j - w[i]] + v[i]);
    }
}

加上h条件

由于当装备背包之后，如果可携带重量没有满，就可以拿一个任意重的东西。所以可以找出当h不为0时可以卡bug的时候的最大值。

		for (int k = 1; k <= n; k++) {//枚举用k来找卡bug 取k的最优解
			memset(f, 0, sizeof(f));
			for (int i = 1; i <= n; i++) {
				if (i == k) {
					for (int j = 0; j <= m + h; j++)
						f[i][j] = f[i - 1][j];
					continue;
				}
				for (int j = 0; j <= m + h; j++) {
					f[i][j] = f[i - 1][j];
					if (j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
				}
			}
			if (h > 0) ans = max(ans, f[n][m + h - 1] + v[k]);
			else ans = max(ans, f[n][m + h]);
		}

完整ac代码

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int m, n, h;
int w[N], v[N];
int f[N][N * 2];// 0<=n,m,h<=100


int main() {
	while (cin >> n) {
		if (n == 0) break;
		cin >> m >> h;
		for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

		int ans = 0;
		for (int k = 1; k <= n; k++) {
			memset(f, 0, sizeof(f));
			for (int i = 1; i <= n; i++) {
				if (i == k) {
					for (int j = 0; j <= m + h; j++)
						f[i][j] = f[i - 1][j];
					continue;
				}
				for (int j = 0; j <= m + h; j++) {
					f[i][j] = f[i - 1][j];
					if (j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
				}
			}
			if (h > 0) ans = max(ans, f[n][m + h - 1] + v[k]);
			else ans = max(ans, f[n][m + h]);
		}
		cout << ans << endl;
	}
	return 0;
}