FATE HDU - 2159 （背包问题）

FATE HDU - 2159 （背包问题）

题意：
有n种物品，每种物品有一个价值和一个体积，你有一个背包，且装入物品的数量不能超过m，问：怎样装物品才能使得总价值超过v，而且背包剩余容量尽可能大。输出最大剩余容量p。
分析：
二维费用完全背包问题。难点在于如何求p。既要总价值超过v，又要剩余容量尽可能小。因为在dp的过程中求的是最大价值，因此背包总价值一定是以最快的速度增加的。所以我们只需要在dp的过程中对总价值超过v的体积求min即可。
代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
int n, m, k, s;
int dp[maxn][maxn];
int c[maxn], v[maxn];

int main()
{
	while (cin >> n >> m >> k >> s)
	{
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= k; i++)
			cin >> v[i] >> c[i];
		int minv = 1e9;
		for (int i = 1; i <= k; i++)
			for (int j = c[i]; j <= m; j++)
				for (int k = 1; k <= s; k++)
				{
					dp[j][k] = max(dp[j][k], dp[j - c[i]][k - 1] + v[i]);
					if(dp[j][k] >= n)
						minv = min(minv, j);
				}
		if (minv == 1e9) cout << -1 << endl;
		else cout << m - minv << endl;
	}
}