01背包 完全背包 多重背包模板

01背包 完全背包 多重背包模板

const int maxn = 100000 + 10;int N, V, amount[maxn], capacity[maxn], weight[maxn];int dp[maxn];void bag01(int cost, int weight) { for (int i = V; i >= cost; i--) { dp[i] = max(dp[i], dp[i - cost] + weight); }}void completebag(int cost, int weight) { for (int i = cost; i <= V; i++) { dp[i] = max(dp[i], dp[i - cost] + weight); }}void multiplybag(int cost, int weight, int amount) { if (cost * amount >= V) completebag(cost, weight); else { int k = 1; while (k < amount) { bag01(k * cost, k * weight); amount -= k; k += k; } bag01(amount * cost, amount * weight); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。