在东营怎么建网站,数商云电子商务网站建设,怎么看出网站是dede做的,wordpress 4.5 安装本题为完全背包 与01背包的区别是 物品可以任意取 而01背包只能取一次
这就导致了状态转移方程的不同 1.当放不下:的时候 转移方程是一样的 取0到i-1 物品#xff0c;背包容量为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(vectorint coins, int amount) {int ncoins.size();vectorvectorintdp(n1,vectorint(amount1,amount1));for(int i0;in;i)dp[i][0]0;for(int i1;in;i){for(int j1;jamount;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( amount1 dp[n][amount])return -1;elsereturn dp[n][amount];}
};
