手机 网站 微信 源码,服务类网站免费建站,重庆建设厂网站,烟台百度网站排名ssl2289-庆功会
Description 为了庆贺班级在校运动会上取得第一名的成绩#xff0c;班主任决定开一场庆功会#xff0c;为此拔款购买奖品奖励运动员#xff0c;期望拔款金额能购买最大价值的奖品#xff0c;可以补充他们的精力和体力。 Input 第一行二个数n(n500)班主任决定开一场庆功会为此拔款购买奖品奖励运动员期望拔款金额能购买最大价值的奖品可以补充他们的精力和体力。 Input 第一行二个数n(n500)m(m5000)其中n代表希望购买的物品的种数m表示班会拨的钱数。 接下来n行每行3个数v、w、s分别表示第I种物品的价格、价值价格 与 价值 是不同的概念和购买的数量只能买0件或s件其中v100,w1000,s10 Output 第一行一个数表示此次购买能获得的最大的价值注意不是价格。 Sample Input 5 1000 80 20 4 40 50 9 30 50 7 20 20 1 Sample Output 1040
解题思路 枚举一下选的组数就好了可以二进制优化。 代码 #includecstdio
#includeiostream
using namespace std;
int n,m,w[501],c[501],s[501],f[6001];
int main()
{scanf(%d%d,n,m);for (int i1;in;i) scanf(%d%d%d,w[i],c[i],s[i]);for (int i1;in;i)for (int jm;j0;j--)for (int k0;ks[i];k)//枚举组数{if (j-k*w[i]0) break;//判断越界f[j]max(f[j],f[j-k*w[i]]k*c[i]);}printf(%d,f[m]);
}二进制优化代码 #includecstdio
#includeiostream
using namespace std;
int n,m,w[10001],c[10001],f[6001],n1;
int main()
{scanf(%d%d,n,m);for (int i1;in;i) {int x,y,s,t1;scanf(%d%d%d,x,y,s);while (st){w[n1]x*t;c[n1]y*t;s-t;t*2;}w[n1]x*s;c[n1]y*s;//二进制优化}for (int i1;in1;i)for (int jm;jw[i];j--)f[j]max(f[j],f[j-w[i]]c[i]);printf(%d,f[m]);
}ssl2301-混合背包
Description 背包体积为V ,给出N个物品每个物品占用体积为Vi,价值为Wi,每个物品要么至多取1件要么至多取mi件mi 1 , 要么数量无限 在所装物品总体积不超过V的前提下所装物品的价值的和的最大值是多少 Input 第一行两个数V,N下面N行每行三个数Vi,Wi,Mi表示每个物品的体积价值与数量Mi1表示至多取一件Mi1表示至多取Mi件Mi0表示数量无限 Output 1个数Ans表示所装物品价值的最大值 Sample Input 10 3 2 1 0 3 3 1 4 5 4 Sample Output 11
解题思路
混合背包就是多重加完全罢了。 代码 #includecstdio
#includeiostream
using namespace std;
int n,m,w[31],c[31],f[201],s[31];
int main()
{scanf(%d%d,m,n);for (int i1;in;i) {scanf(%d%d%d,w[i],c[i],s[i]);}for (int i1;in;i)if (s[i]0){for (int jw[i];jm;j)f[j]max(f[j],f[j-w[i]]c[i]);}//完全背包else{for (int j1;js[i];j)for (int km;kw[i];k--)f[k]max(f[k],f[k-w[i]]c[i]);}//多重printf(%d,f[m]);
} ssl2291-分组背包
Description
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]价值是w[i]。这些物品被划分为若干组每组中的物品互相冲突最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量且价值总和最大。 Input 第一行三个整数v(背包容量v200),n物品数量n30)和t最大组号t10; 第2..n1行每行三个整数wi,ci,p表示每个物品的重量、价值、所属组号。 Output 仅一行一个数表示最大总价值。 Sample Input 10 6 3 2 1 1 3 3 1 4 8 2 6 9 2 2 8 3 3 9 3 Sample Output
20 解题思路
分组背包枚举一遍就好了。 代码 #includecstdio
#includeiostream
using namespace std;
int w[31],c[31],a[11][32],f[201],m,n,t,p;
int main()
{scanf(%d%d%d,m,n,t);for (int i1;in;i){scanf(%d%d%d,w[i],c[i],p);a[p][a[p][0]]i;//分组}for (int i1;it;i)for (int jm;j0;j--)for (int k1;ka[i][0];k)//枚举选的组数if (jw[a[i][k]])//避免越界{f[j]max(f[j],f[j-w[a[i][k]]]c[a[i][k]]);//动态转移}printf(%d,f[m]);
}ssl1115-货币系统
Description 母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。 [In their own rebellious way]他们对货币的数值感到好奇。 传统地一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。 母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。 举例来说, 使用一个货币系统 {1,2,5,10,...}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x22x1, 3x521,等等其它。 写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。 保证总数将会适合long long (C/C) 和 Int64 (Free Pascal)。 Input 货币系统中货币的种类数目是 V 。 (1 V25) 要构造的数量钱是 N 。 (1 N10,000) 第 1 行: 二整数 V 和 N 第 2 ..V1行 可用的货币 V 个整数 (每行一个 每行没有其它的数)。 Output 单独的一行包含那个可能的构造的方案数。 末尾有空行 Sample Input 3 10 1 2 5 Sample Output 10
解题思路 方案数问题用累加前面可能出现的情况 代码 #includecstdio
using namespace std;
int a[10001],n,m;
long long f[10001];
int main()
{scanf(%d%d,n,m);for (int i1;in;i)scanf(%d,a[i]);//输入f[0]1;//预处理for (int i1;in;i)for (int ja[i];jm;j)f[j]f[j-a[i]];//方案数累加printf(%lld,f[m]);
}
