做网站优化词怎么选择,制造网站建设哪家好,建网站科技公司,东莞模板建站软件逃亡的准备逃亡的准备逃亡的准备
ssl 1236 类似一样题目#xff08;除数组范围外#xff09;:ssl 2289#xff08;庆功会#xff09;
题目大意#xff1a;
有n个物品#xff0c;每个物品可以选l[i]个,每个的代价为a[i],价值为b[i]#xff0c;在代价不大于m的情况下除数组范围外:ssl 2289庆功会
题目大意
有n个物品每个物品可以选l[i]个,每个的代价为a[i],价值为b[i]在代价不大于m的情况下价值最大是多少 Description
在《Harry Potter and the Deathly Hallows》中Harry Potter他们一起逃亡现在有许多的东西要放到赫敏的包里面但是包的大小有限所以我们只能够在里面放入非常重要的物品现在给出该种物品的数量、体积、价值的数值希望你能够算出怎样能使背包的价值最大的组合方式并且输出这个数值赫敏会非常地感谢你。
Input
1第一行有2个整数物品种数n和背包装载体积v。
22行到n1行每行3个整数为第i种物品的数量m、体积w、价值s。
Output
仅包含一个整数即为能拿到的最大的物品价值总和。
Sample Input
2 10
3 4 3
2 2 5
Sample Output
13
Hint
【注释】
选第一种一个第二种两个。
结果为3×15×213
【数据规模】
对于30%的数据
1v500
1n2000
1m10
1w20
1s100
对于100%的数据
1v500
1n2000
1m5000
1w20
1s100 TLE{\color{Red} TLE}TLE方法
注释
小数据可以用
在01背包的基础上加上一重循环来枚举种数就可以TLE了
#includecstdio
#includeiostream
using namespace std;
int n,m,l,v,s,f[505];
int main()
{scanf(%d%d,n,m);for (int i1;in;i){scanf(%d%d%d,l,v,s);for (int jm;jv;j--)for (int k0;kl;k)//加个k用于枚举种数if (jv*k)//判断出界未f[j]max(f[j],f[j-v*k]s*k);//代价和}printf(%d,f[m]);
}AC{\color{Blue} AC}AC方法
将每一种物品的数量分为不同的组每一组是上一组的两倍比如有3个时分为1个和2个这样1就直接用1,2就直接用2,3就用1加2
当有四个时就是1,2,1因为首先要保证总和与l一样其次4就是121,1怎么来的呢1×2×24但4-1-就只剩下1了,14所以就直接用1否则两倍两倍地乘
#includecstdio
#includeiostream
#includecstring
using namespace std;
int n,m,w,l,x,y,t,s[50005],v[50005],f[505];
int main()
{scanf(%d%d,n,m);for (int i1;in;i){scanf(%d%d%d,l,x,y);t1;//原本为1while (lt)//判断是否可以存{v[w]x*t;//w为总个数代价要加倍s[w]y*t;//价值也要加倍l-t;//l为剩下的t*2;//t翻倍}if (l)//判断是否有{v[w]x*l;//存s[w]y*l;//再存}}for (int i1;iw;i)for (int jm;jv[i];j--)f[j]max(f[j],f[j-v[i]]s[i]);//当做01背包来做printf(%d,f[m]);
}
