NYOJ 654 喜歡玩warcraft的ltl (01背包常數優化)

NYOJ 654 喜歡玩warcraft的ltl (01背包常數優化)

一個常數優化

前面的偽代碼中有 for v=V..1，可以將這個循環的下限進行改進。

由於只需要最後f[v]的值，倒推前一個物品，其實只要知道f[v-w[n]]即可。以此類推，對以第j個背包，其實只需要知道到f[v-sum{w[j..n]}]即可，即代碼中的

for i=1..N

    for v=V..0

可以改成

for i=1..n

    bound=max{V-sum{w[i..n]},c[i]}

    for v=V..bound

這對於V比較大時是有用的。

/*
* Problem: NYOJ No.654
* Running time: 412MS
* Complier: C++
* Author: ACM_herongwei
* Create Time: 9:24 2015/9/9 星期三 
* zeroonebags 的常數優化
*/
#include 
#include 
#include 
#include 
#define CLR(c,v) (memset(c,v,sizeof(c)))
using namespace std;

template 
inline _T Max(_T a,_T b){
	return (a>b)?(a):(b);
}
template 
inline _T Max(_T a,_T b,_T c){
	return (a>Max(b,c))?(a):(Max(b,c));
}
const int COST =  1e6 + 10;
const int M    =  1e4 + 10;

int dp[COST];
int value[M];
int volume[M];

int main(){
	int Ncase;
	scanf(%d,&Ncase) ;
	while(Ncase--){
		CLR(dp,0);
		int max_cost, n_bags;
		scanf(%d%d,&n_bags, &max_cost);
		for (int i = 0 ; i < n_bags ; ++i){ // max:1000
			scanf(%d%d,&volume[i],&value[i]);
		}
		for (int i = 0 ; i < n_bags ; ++i){ // max:1000
			int sum = 0;
			for(int j = i ; j < n_bags ; ++j){
				sum += volume[j];
			}
			int bound = Max(max_cost-sum , volume[i]);
			for(int j = max_cost ; j >= bound ; j--){ // max:100 0000
				if( dp[j] < dp[j-volume[i]] + value[i]){
					dp[j] = dp[j-volume[i]] + value[i];
				}
			}
		}
		printf(Max experience: %d
,dp[max_cost]);
	}
	return 0;
}
/*
樣例輸入
2
3 10
7 7
2 3
3 5
2 5
3 5
2 1
樣例輸出
Max experience: 12
Max experience: 6
*/