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;
}