POJ 3624 Charm Bracelet 背包问题的解决方案

最简单的背包问题，标题应该是除了背包测试中心：您无法打开二维数组。我还没有开的二维。光看数据是不可能的。

太大。

有两种方法来提高全省内存DP：

1 所谓卷的阵列

2 反向表

久没做背包DP，突然认为这样的背包问题非常easy了。

以下给出两种解法:

1 calBag()是滚动数组

2 calBag2()是逆向填表

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <vector>
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<vector<int> > tbl(2, vector<int>(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
", calBag2());
	}
	return 0;
}