当前位置: 首页 > news >正文

制作一个收费网站要多少钱html友情链接

制作一个收费网站要多少钱,html友情链接,wordpress按修改时间排序,phpstudy网站建设教程混合背包是指多种背包模型的组合与转化。 下面通过题目加深理解。 题目一 测试链接:1742 -- Coins 分析:这道题可以通过硬币的个数将其转化为01背包,完全背包和多重背包。如果硬币的个数是1个,则是01背包;如果硬币的…

混合背包是指多种背包模型的组合与转化。

下面通过题目加深理解。

题目一

测试链接:1742 -- Coins

分析:这道题可以通过硬币的个数将其转化为01背包,完全背包和多重背包。如果硬币的个数是1个,则是01背包;如果硬币的面值×硬币的个数大于当前需要找零的数额,则是完全背包;否则是多重背包。对于不同的背包进行不同的可能性展开,最后统计,即可得到答案。代码如下。

#include <iostream>
using namespace std;
int n, m;
int number, ans_index = 0;
int coin[100][2];
bool dp[100001];
int ans[100];
int main(void){scanf("%d%d", &n, &m);while (!(n == 0 && m == 0)){number = 0;for(int i = 0;i < n;++i){scanf("%d", &coin[i][0]);}for(int i = 0;i < n;++i){scanf("%d", &coin[i][1]);}for(int i = 1;i <= m;++i){dp[i] = false;}dp[0] = true;for(int i = 0;i < n;++i){if(coin[i][1] == 1){for(int j = m;j >= 0 && j - coin[i][0] >= 0;--j){dp[j] |= dp[j-coin[i][0]];}}else if(coin[i][0] * coin[i][1] > m){for(int j = 0;j <= m;++j){if(j - coin[i][0] >= 0){dp[j] |= dp[j-coin[i][0]];}}}else{for(int j = m;j >= 0;--j){for(int k = 1;k <= coin[i][1] && j - k * coin[i][0] >= 0;++k){dp[j] |= dp[j-k*coin[i][0]];}}}}for(int i = 1;i <= m;++i){if(dp[i]){++number;}}ans[ans_index++] = number;scanf("%d%d", &n, &m);}for(int i = 0;i < ans_index;++i){printf("%d\n", ans[i]);}return 0;
}

其中,求dp数组循环中,i为在下标0~i的物品中取。当然,这道题其实可以直接将其当作一个多重背包,二进制优化后转化为01背包进行求解。代码如下。

#include <iostream>
using namespace std;
int n, m;
int data_index, temp, number, ans_index = 0, coin_num;
int coin[100];
bool dp[100001];
int data[1001];
int ans[100];
int main(void){scanf("%d%d", &n, &m);while (!(n == 0 && m == 0)){data_index = 0;number = 0;for(int i = 0;i < n;++i){scanf("%d", &coin[i]);}for(int i = 0;i < n;++i){scanf("%d", &coin_num);temp = 1;while (coin_num >= temp){data[data_index++] = temp * coin[i];coin_num -= temp;temp *= 2;}if(coin_num > 0){data[data_index++] = coin_num * coin[i];}}for(int i = 1;i <= m;++i){dp[i] = false;}dp[0] = true;for(int i = 0;i < data_index;++i){for(int j = m;j >= 0 && j - data[i] >= 0;--j){dp[j] |= dp[j-data[i]];}}for(int i = 1;i <= m;++i){if(dp[i]){++number;}}ans[ans_index++] = number;scanf("%d%d", &n, &m);}for(int i = 0;i < ans_index;++i){printf("%d\n", ans[i]);}return 0;
}

http://www.zhongyajixie.com/news/18765.html

相关文章:

  • 淘宝网站建设方案seo网站诊断方案
  • 考试网站建设b2b网站大全免费
  • 免费效果图网站什么是关键词广告
  • 工商局网站查询入口免费关键词挖掘网站
  • 网站开发前后端配比哪家公司做推广优化好
  • 南京网站建设有限公司精准客源推广引流
  • 网站制作接单平台活动策划
  • 用什么做网站后台烟台seo外包
  • 商业空间设计图片seo运营做什么
  • 网站优化代码青岛seo精灵
  • 南昌高端模板建站iis7站长工具
  • 做公司网站的平台中国疫情最新消息
  • 网站建设职业发展前景打开百度搜索网站
  • 广州学校论坛网站建设天津网站建设公司
  • 成都网站建设外包太原百度seo排名软件
  • 天津外贸公司网站制作seo关键词排名优化销售
  • 怎么用手机搭建网站百度网盘官网登陆入口
  • 郑州模板网站建设策划公司公众号排名优化
  • 用jsp做留言板网站现在最火的推广平台
  • 做家旅游的视频网站好网站优化排名软件推广
  • 江都建设招标网站seo优化需要多少钱
  • 网站优化关键词怎么做企业推广策划
  • 做任务赚佣金网站有哪些百度收录情况查询
  • 作文网投稿网站seo站长工具下载
  • 基于jquery做的网站如何关闭2345网址导航
  • 温州 网站建设网络推广都有哪些平台
  • 可以做私募股权投资的网站百度广告屏蔽
  • 只做原创内容平台网站一个新产品策划方案
  • 安徽做手机网站郑州网站制作推广公司
  • 怎么在网站里做关键词优化流量平台有哪些