POJ2184 Cow Exhibition(DP: 변종 01 백팩)

제목:
한 무리의 젖소는 각각 s와 f 두 개의 값이 있는데 일부 젖소는 s와 f의 값을 가장 크고 s와 f의 값을 마이너스로 할 수 없도록 선택해야 한다.
주요 사항:
dp[i]=j로 s의 합이 i일 때 f의 합이 j라는 것을 표시하고 마지막으로 dp[i]+i의 최대치만 요구하면 된다.이 문제는 음수가 있기 때문에 편이량을 도입해야 한다.여기에 01가방은 1차원으로 표시되기 때문에 s[i]의 양과 음에 따라 각각 처리해야 한다. 역순인지 양순인지 주로 서브구조가 먼저 업데이트되지 않도록 고려해야 한다.
15913695
Seasonal
2184
Accepted
1036K
172MS
C++
838B
2016-08-07 20:47:38

#include
#include
using namespace std;
const int shift = 1000*100;
const int inf = 0x3f3f3f;

int main()
{
	int dp[2 * shift+105],s[105],f[105];
	int n,i,j;
	while (cin >> n)
	{
		for (i = 0; i < n; i++)
			cin >> s[i] >> f[i];
		for (i = 0; i <= 2 * shift + 104; i++)
			dp[i] = -inf;
		dp[shift] = 0;
		for (i = 0; i < n; i++)
		{
			if (s[i] <= 0 && f[i] <= 0)
				continue;
			if (s[i] >= 0)
			{
				for (j = 2 * shift; j >= s[i]; j--)
					if (dp[j - s[i]] > -inf)
						dp[j] = max(dp[j], dp[j - s[i]] + f[i]);//  j-s[i] -inf)
						dp[j] = max(dp[j], dp[j - s[i]] + f[i]);//  j-s[i]>j         j-s[i]      ，     ，     
			}
		}
		int ans = -inf;
		for (i = shift; i <= 2 * shift+100; i++)
			if(dp[i]>=0)
				ans = max(ans, dp[i]+i-shift);
		cout << ans << endl;
	}
	return 0;
}

전재 대상:https://www.cnblogs.com/seasonal/p/10343705.html