宁波网站建设培训,微信小程序开发平台官网,阳江网络问政平台,北京建设网站公司来源hdu2602 问题描述 许多年前#xff0c;在泰迪的家乡#xff0c;有一个人被称为“骨头收藏家”。这个男人喜欢收集各种各样的骨头#xff0c;比如狗狗#xff0c;牛#xff0c;还有他去了坟墓...... 骨头收藏家有一个大容量的V袋#xff0c;沿着他的收集之旅有很多骨头… 来源hdu2602 问题描述 许多年前在泰迪的家乡有一个人被称为“骨头收藏家”。这个男人喜欢收集各种各样的骨头比如狗狗牛还有他去了坟墓...... 骨头收藏家有一个大容量的V袋沿着他的收集之旅有很多骨头显然不同的骨骼具有不同的值和不同的体积现在根据他的行程给出每个骨骼的值你能计算出骨骼采集器可以得到的总值的最大值吗 输入 第一行包含整数T个案数。 接下来是T个案例每个案例有三行第一行包含两个整数NVN 1000V 1000表示骨骼的数量和他的包的体积。第二行包含表示每个骨骼值的N个整数。第三行包含表示每个骨骼体积的N个整数。 输出 每行一个整数表示总值的最大值此数字将小于2 31。 样本输入 1 5 10 1 2 3 4 5 5 4 3 2 1 样本输出 14 最基础01背包判断第i件要不要放进去状态转移方程dp[i][V]max{dp[i-1][V],dp[i-1][V-v[i]]w[i]} “将前i件物品放入容量为v的背包中”这个子问题若只考虑第i件物品的策略放或不放那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品那么问题就转化为“前i-1件物品放入容量为v的背包中”如果放第i件物品那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 #includeiostream
#includestdio.h
#includestdlib.h
#include iomanip
#includecmath
#includefloat.h
#includestring.h
#includealgorithm
#define sf scanf
#define pf printf
#define scf(x) scanf(%d,x)
#define scff(x,y) scanf(%d%d,x,y)
#define prf(x) printf(%d\n,x)
#define mm(x,b) memset((x),(b),sizeof(x))
#includevector
#includequeue
#includemap
#define rep(i,a,n) for (int ia;in;i)
#define per(i,a,n) for (int ia;in;i--)
typedef long long ll;
const ll mod1e9100;
const double eps1e-8;
using namespace std;
const double piacos(-1.0);
const int N1005;
int dp[N][N];
int w[N],v[N];
int main()
{int re,V,n;scf(re);v[0]0;w[0]0;while(re--){mm(dp,INT_MIN);scff(n,V);rep(i,1,n1)scf(w[i]);rep(i,1,n1)scf(v[i]);rep(i,1,n1)//第i件物品 rep(j,0,V)//空间为j的时候 {if(v[i]j)dp[i][j]max(dp[i-1][j],dp[i-1][j-v[i]]w[i]);elsedp[i][j]dp[i-1][j];}prf(dp[n][V]);}return 0;
} 一维 #includeiostream
#includestdio.h
#includestdlib.h
#include iomanip
#includecmath
#includefloat.h
#includestring.h
#includealgorithm
#define sf scanf
#define pf printf
#define scf(x) scanf(%d,x)
#define scff(x,y) scanf(%d%d,x,y)
#define prf(x) printf(%d\n,x)
#define mm(x,b) memset((x),(b),sizeof(x))
#includevector
#includequeue
#includemap
#define rep(i,a,n) for (int ia;in;i)
#define per(i,a,n) for (int ia;in;i--)
typedef long long ll;
const ll mod1e9100;
const double eps1e-8;
using namespace std;
const double piacos(-1.0);
const int N1e35;
int dp[N];
int w[N],v[N];
int main()
{int re,V,n;scf(re);while(re--){mm(dp,0);scff(n,V);rep(i,1,n1)scf(w[i]);rep(i,1,n1)scf(v[i]);rep(i,1,n1){per(j,V,v[i])dp[j]max(dp[j],dp[j-v[i]]w[i]);}prf(dp[V]);}return 0;
} 转载于:https://www.cnblogs.com/wzl19981116/p/9487625.html
