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

天津外贸网站建设公司市场营销推广策划

天津外贸网站建设公司,市场营销推广策划,国外优秀网站建设公司,辽宁沈阳疫情最新消息本题为完全背包 与01背包的区别是 物品可以任意取 而01背包只能取一次 这就导致了状态转移方程的不同 1.当放不下:的时候 转移方程是一样的 取0到i-1 物品,背包容量为j的最优值 else 2.放得下:就是取 0到i-1 物品,背包容量为j的最优值和 “0到i的[j-w[i]]v…

本题为完全背包 与01背包的区别是 物品可以任意取 而01背包只能取一次

这就导致了状态转移方程的不同

1.当放不下:的时候 转移方程是一样的 取0到i-1 物品,背包容量为j的最优值

else

2.放得下:就是取    0到i-1 物品,背包容量为j的最优值和    “0到i的[j-w[i]]+v[i]"

                                                                                          (或者是本题中把v[i]改成加1)”

区别说得再简单一点就是01背包放第i件物品后+dp[i-1][j-w[i]] 

                                        完全背包则是放第i件物品后+dp[i][j-w[i]]

为什么一个取上一行,另一个取本行?

答:上一行是0-上一个物品的最优值,01背包取了就不能再取了

       本行是0-本物品的最优值,完全背包取了还可以再取

那完全背包光取本行物品了别的物品不混合放了?

答: 这里我们就当本物品的w[i]>j直接不取 就用dp[i-1][j],

所以我们的dpij是可能会加上w[i]>j 时的dp[i-1][j]

本题如何初始化

最左一列全部初始化为0 j-w[j]==0的时候硬币数为0

第一行取最大值 因为每个dpij都是要与dpi-1 j比小的

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int n=coins.size();vector<vector<int>>dp(n+1,vector<int>(amount+1,amount+1));for(int i=0;i<=n;i++)dp[i][0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=amount;j++){if(coins[i-1]>j){dp[i][j]=dp[i-1][j];}elsedp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1);}}if(    amount+1==  dp[n][amount])return -1;elsereturn dp[n][amount];}
};

http://www.ds6.com.cn/news/36967.html

相关文章:

  • 极速网站开发好的竞价账户托管外包
  • 商标 做网站 是几类长沙网络营销公司
  • 做网站常用的英文字体网络营销网站建设
  • 千库网网站杭州百度首页优化
  • 建网站多少网站seo思路
  • 帮企业做网站赚钱seo如何优化一个网站
  • 温州专业微网站制作公司品牌推广计划书怎么写
  • 吉林网站备案电脑优化大师哪个好
  • 做论坛网站的元素云南省最新疫情情况
  • 大连app开发公司排名成都seo推广员
  • 为什么网站突然打不开搜索引擎优化的英文
  • 任县网站制作360投放广告怎么收费
  • 安徽搜索引擎推广平台网站seo优化服务
  • 什么是网站建设如何宣传自己的网站
  • 嘉善县建设工程管理与监督网站活动营销推广方案
  • 做app和网站哪个比较好搜索引擎的工作原理是什么?
  • WordPress开网站很慢最佳磁力吧ciliba搜索引擎
  • 印刷个性化网站建设的意义线上推广100种方式
  • 网站一年多少钱北京seo分析
  • 时时彩网站代理怎么做?广告宣传费用一般多少
  • 大连科技学院官方网站的建设与放软文时光发稿平台
  • web网站开发的设计思想爱站网的关键词是怎么来的
  • 宁夏做网站建设公司关键词的选取原则有
  • 有可以做推广的网站吗上海网站建设开发
  • 优秀个人网站网站如何才能被百度收录
  • 照明灯具类企业网站广告推广平台网站有哪些
  • 宁波做网站搜索引擎的作用
  • 网站域名使用怎么做分录最新的疫情防控政策和管理措施
  • 黄浦网站建设网络营销师报名入口
  • 怎么建设淘客自己的网站、国际新闻头条今日要闻