HDU 2955 Robberies (아이디어 문제 & 0 - 1 가방)

1180 단어 C++ACM배낭HDU
http://acm.hdu.edu.cn/showproblem.php?pid=2955
어떻게 변형 하나 요?
int _01pack(int n, int maxw)
{
	memset(dp, 0, sizeof(dp));
	dp[0] = 1.0;///     
	int i, j;
	for (i = 0; i < n; ++i)
		for (j = maxw; j >= w[i]; --j)///maxw          
			dp[j] = max(dp[j], dp[j - w[i]] * v[i]);
	for (i = maxw;; --i) if (dp[i] >= p) return i;///     
}

전체 코드:
/*109ms,312KB*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx = 105;

int w[mx];
double v[mx], dp[10005], p;

int _01pack(int n, int maxw)
{
	memset(dp, 0, sizeof(dp));
	dp[0] = 1.0;
	int i, j;
	for (i = 0; i < n; ++i)
		for (j = maxw; j >= w[i]; --j)
			dp[j] = max(dp[j], dp[j - w[i]] * v[i]);
	for (i = maxw;; --i) if (dp[i] >= p) return i;
}

int main()
{
	int t, n, maxw, i;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%lf%d", &p, &n);
		p = 1.0 - p;
		maxw = 0;
		for (i = 0; i < n; ++i)
		{
			scanf("%d%lf", &w[i], &v[i]);
			maxw += w[i];
			v[i] = 1.0 - v[i];
		}
		printf("%d
", _01pack(n, maxw)); } return 0; }

좋은 웹페이지 즐겨찾기