Java教程

背DP

本文主要是介绍背DP,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<bits/stdc++.h>
using namespace std;
const int z = 1024;
int packdp[z][z];
void ngokpack(int p,int v,int V) {
	for(int i = V;i >= v;++i)
		packdp[1][z] = max(packdp[1][z],packdp[1][i-v]+p);
}//零一背包; 
void fullpack(int p,int v,int V) {
	for(int i = v;i <= V;++i)
		packdp[1][z] = max(packdp[1][z],packdp[1][i-v]+p);
}//完全背包;
void mutipack(int &p,int &v,int n,int &V) {
	if(v*n > V) {
		fullpack(p,v,V);
	} else {
		int k = 1;
		while(n-k >= 0) {
			ngokpack(k*p,k*v,V);
			n -= k;
			k *= 2;
		}
		ngokpack(n*p,n*v,V);
	}
}//混合背包(内含多重背包);
void dbnkpack(int &p,int &ti,int &vi,int &T,int &V) {
	for(int i = T;i >= ti;++i)
		for(int j = V;j >= vi;++j) 
			packdp[i][j] = max(packdp[i][j],packdp[i-ti][j-vi]+p);
}//二维背包; 
void gruppack(int *gp,int *gv,int &V) {
	for(int i = V;i >= 0;--i)
		for(int j = 1;j <= gp[0];++j)
			if(i >= gv[j])
				packdp[1][i] = max(packdp[1][i],packdp[1][i-gv[j]]+gp[j]);
}//分组背包; 
int main() {
	//to do;
	//所有的背包在主函数引用时须包一层循环,循环物品或组的个数; 
}

 

这篇关于背DP的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!