多软件网站下载安装,手机wap 网站,org是国外的网站吗,a站HDU链接 文章目录题目描述#xff1a;题意#xff1a;题解#xff08;代码#xff09;题目描述#xff1a; 输入描述: 输出描述: For each test case output the answer on a single line. 输入
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0输出
8
4题意#xff1a;
有n种硬币题意题解代码题目描述 输入描述: 输出描述: For each test case output the answer on a single line. 输入
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0输出
8
4题意
有n种硬币面额分别是Ai每种硬币数量分别是Ci问这些硬币能组成1~m中多少个数 样例分析 3 10 1 2 4 2 1 1 有2个一元1个两元1个四元可以组成1,234,567,89和10无法组成能组成的一共八个
题解
如果还没学习背包问题的知识看这里 混合背包问题 可以用二进制的方法来优化 背包问题中常见的三个元素体积所占容量价值数量 在本题中硬币的价值即是体积也是价值A[i]数量为硬币的数量C[i] 容量上限是m 当cam时也就是一种货币的金额就超过m时我们可以当做是完全背包即将这种货币看做无数个因为货币的数量乘以金额已经超过上限所以再多也没有影响。这一部分用完全背包的做法 当cam时我们就当做多重背包来做将多重背包进行二进制优化用01背包的解法来做 具体看代码
代码
含详细讲解
#includebits/stdc.h
using namespace std;
const int maxn1e55;
int dp[maxn];
int a[120],c[120];
int n,m;
void zeroone(int cost,int val)
{for(int im;icost;i--){dp[i]max(dp[i],dp[i-cost]val);}
}
void wanquanbeibao(int cost,int val)
{for(int icost;im;i)dp[i]max(dp[i],dp[i-cost]val);
}
void cal(int cost,int val,int num)
{if(cost*numm)wanquanbeibao(cost,val);//完全背包不必考虑数量else {for(int i1;inum;i1){zeroone(i*cost,i*val);//乘以对应的系数 num-i; }zeroone(num*cost,num*val);//剩余部分处理 }
}
int main()
{while(cinnm(nm)){memset(dp,0,sizeof(dp));for(int i1;in;i)cina[i];for(int i1;in;i)cinc[i];for(int i1;in;i){cal(a[i],a[i],c[i]);//花费价值数量 }int sum0;for(int i1;im;i){if(dp[i]i)sum;}coutsumendl;}return 0;
}
