程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> NYOJ 654 喜歡玩warcraft的ltl (01背包常數優化)

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

編輯:關於C++

 

 

一個常數優化

 

前面的偽代碼中有 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
*/


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved