频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 3624 Charm Bracelet 背包题解
2014-06-27 11:10:24         来源:POJ 3624 Charm Bracelet 背包题解  
收藏   我要投稿

最简单的背包问题了,本题应该除了背包就一个考点了:不能开二维数组。我没开过二维,不过看数据是不可以的。太大了。

做法有两种改进省内存DP:

1 所谓的滚动数组

2 逆向填表


很久没做背包DP,突然觉得这种背包问题很简单了。

下面给出两种解法:

1 calBag()是滚动数组

2 calBag2()是逆向填表


#pragma once
#include 
#include 
#include 
using namespace std;

const int MAX_W = 12881;
const int MAX_N = 3403;
int N, M;//M是total weight
int wei[MAX_N];
int desi[MAX_N];
int tbl[MAX_W];

int calBag2()
{
	memset(tbl, 0, sizeof(int)*(M+1));
	for (int i = 1; i <= N; i++)
	{
		for (int j = M; j >= wei[i]; j--)
			tbl[j] = max(tbl[j], tbl[j-wei[i]]+desi[i]);
	}
	return tbl[M];	
}

int calBag()
{
	vector > tbl(2, vector(M+1));
	bool id = true;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j < wei[i] && j <= M; j++) tbl[id][j] = tbl[!id][j];
		for (int j = wei[i]; j <= M; j++)
		{
			tbl[id][j] = max(tbl[!id][j], tbl[!id][j-wei[i]]+desi[i]);
		}//注意都是上一列的数据往下拉,都是!id数列比较
		id = !id;
	}
	return tbl[!id][M];
}

int main()
{
	while (scanf("%d %d", &N, &M) != EOF)
	{
		for (int i = 1; i <= N; i++)
		{
			scanf("%d %d", &wei[i], &desi[i]);
		}
		printf("%d\n", calBag2());
	}
	return 0;
}






点击复制链接 与好友分享!回本站首页
相关TAG标签 题解 背包
上一篇:打印1到最大的n位数
下一篇:局部静态变量的多线程问题
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站