POJ 3624 Charm Braceletリュックサック問題の解決策

最も簡単なリュックサックの問題は、リュックサックテストセンターを除いて、2 D配列を開くことができません.私はまだ2次元を開いていません.データを見るだけでは不可能です.
大きすぎます.
全省メモリDPを向上させるには、次の2つの方法があります.
1いわゆるボリュームのアレイ
2リバーステーブル
久しぶりにバックパックDPをしていたら、急にこのようなバックパックの問題はとてもeasyだと思った.
次の2つの解法を示します.
1 calBag()はスクロール配列です
2 calBag 2()は逆記入表です

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

筆者の心臓は穏やかで、景空間の住所:http://blog.csdn.net/kenden23/、作者の同意なしに転載することはないかもしれません.