主页
分类
标签
时间线
歌单
友链
关于
主页
分类
标签
时间线
歌单
友链
关于
叔叔我啊
主页
分类
标签
时间线
歌单
友链
关于
多重背包
例题 有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 M[i] 件可用，每件耗费的空间是 C[i] ，价值是 W[i] 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。 思路 根据 01 背包的方式， ， 代码 #include <cstdio> #include <iostream> using namespace...
2021-02-13
ACM
动态规划
阅读全文
完全背包
例题 有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 C[i] ，价值是 W[i] 。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。 思路 按照 01 背包相同的思路， 代码 #include<cstdio> #include<iostream> #define maxn 1000...
2021-02-12
ACM
动态规划
阅读全文
01 背包
例题 有 N 件物品和一个容量为 V 的背包。放入第 i 件物品占用的容量是 C[i] ，得到的价值是 W[i] 。求解将哪些物品装入背包可使价值总和最大。 思路 物品仅有两种状态，即放与不放。 如果不放第 i 件物品，那么最大价值为 F[i - 1,v] ；如果放第 i 件物品，那么价值就是 F[i - 1,v - C[i]] 再加上通过放入第 i 件物品获得的价值 W[i] 。 代码 ...
2021-02-11
ACM
动态规划
阅读全文
