首页 > 其他 > 详细

POJ 2063 Investment / 体积变大的完全背包

时间:2014-03-29 02:45:00      阅读:397      评论:0      收藏:0      [点我收藏+]

完全背包  体积都是1000的倍数 所以可以除以1000 可能你会想价值是1000的倍数啊 这没关系

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int dp[maxn];
int a[12];
int b[12];
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int sum, n, m, p;
		scanf("%d %d %d", &sum, &p, &n);
		for(int i = 1; i <= n; i++)
		{
			scanf("%d %d", &a[i], &b[i]);
			a[i] /= 1000;
		}
		while(p--)
		{
			m = sum;
			m /= 1000;
			memset(dp, 0, sizeof(dp));
			for(int i = 1; i <= n; i++)
			{
				for(int j = a[i]; j <= m; j++)
				{
					dp[j] = max(dp[j], dp[j-a[i]]+b[i]);
				}
			}
			sum += dp[m];
		}
		printf("%d\n", sum);
	}
	return 0;
}


 

POJ 2063 Investment / 体积变大的完全背包,布布扣,bubuko.com

POJ 2063 Investment / 体积变大的完全背包

原文:http://blog.csdn.net/u011686226/article/details/22416393

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!