背包模板

tonyfang posted @ 2015年9月02日 20:56 in 随笔 with tags c++ OI , 458 阅读

背包模板来啦~

01背包:$O(VN)$:$f[i,j]=max(f[i-1,j-need[i]]+value[i])$

完全背包:可以优化到$O(VN)$,$f[i,j]=max(f[i,j-k*need[j]]+k*value[i]) (k \times need[j] < maxW)$

多重背包,$O(V\sum_{i=1}^{N} log_{2}^{n_i})$,和完全背包类似的推法。等下看看单调队列优化。

模板来了~

 

# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
const int INF=10000000;
const int Maxn=110,MaxN=100010,MaxW=80010;
int N,W,n,need[MaxN],value[MaxN],f[MaxW];
inline int normalpack() {
	memset(f,0,sizeof(f));
	for (int i=1;i<=N;++i)
		for (int j=W;j>=need[i];--j) 
			f[j] = max(f[j], f[j-need[i]]+value[i]);
	return f[W];
}
inline int zeroonepack() {
	scanf("%d%d",&N,&W);
	for (int i=1;i<=n;++i)
		scanf("%d%d",&need[i],&value[i]);
	return normalpack();	
}
inline int fullpack() {
	scanf("%d%d",&N,&W);
	for (int i=1;i<=N;++i)
		scanf("%d%d",&need[i],&value[i]);
	//memset(f,0,sizeof(f));
	for (int i=1;i<=N;++i) f[i]=-210000;
	for (int i=1;i<=N;++i)
		for (int j=need[i];j<=W;++j) 
			f[j] = max(f[j], f[j-need[i]]+value[i]);
	return f[W];
}
inline int multipack() {
	scanf("%d%d",&n,&W);
	while(n--) {
		int Tneed,Tvalue,Tn,Prefix=1;
		scanf("%d%d%d",&Tn,&Tneed,&Tvalue);
		while(Tn - Prefix >= 0) {
			need[++N]=Tneed*Prefix;
			value[N]=Tvalue*Prefix;
			Tn -= Prefix;
			Prefix <<= 1;
		}
		if(Tn) {
			need[++N]=Tneed*Tn;
			value[N]=Tvalue*Tn;
		}
	}
	/*
	printf("---debug---\n");
	for (int i=1;i<=N;++i)
		printf("No.%d: need:%d, value:%d\n",i,need[i],value[i]);
	printf("---end-of-debug---\n");
	*/
	return normalpack();
}
main() {
	return 0;
}
boardmodelpaper.com 说:
2024年1月06日 17:07

The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter