首页 / C++ / [C++]01背包问题
[C++]01背包问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[C++]01背包问题,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1987字,纯文字阅读大概需要3分钟。
内容图文
![[C++]01背包问题](/upload/InfoBanner/zyjiaocheng/646/8e78ab1f3a0748d2b2faffdd0f15a1b2.jpg)
1.基本问题
有N件物品和一个容量为V 的背包。放入第\(i\)件物品耗费的空间是\(C_i\),得到的价值是\(W_i\)。求解将哪些物品装入背包可使价值总和最大。
1.1 思路
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即\(F[i,v]\)表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:
\(F[i, v] = max\{F[i?1,v], F[i?1,v?C_i] + W_i\}\)
1.2 核心代码
memset(F[0], 0, sizeof(F[0]));
for (int i = 1; i <= n; ++i) {
for (int v = 0; v <= V; ++v) {
if (v >= c[i]) F[i][v] = max(F[i-1][v], F[i-1][v-c[i]] + w[i]);
else F[i][v] = F[i-1][v];
}
}
for (int i = 0; i <= V; ++i) ans = max(ans, F[n][i]);
其时间复杂度和空间复杂度都是\(O(NV)\), 其中时间复杂度基本上不能再优化了,但空间复杂度却可以优化到\(O(V)\)。
memset(F, 0, sizeof(F));
for (int i = 1; i <= n; ++i) {
for (int v = V; v >= c[i]; --v) {
F[v] = max(F[v], F[v-c[i]] + w[i]);
}
}
for (int i = 0; i <= V; ++i) ans = max(ans, F[i]);
2.求方案数
看一道题:小A点菜
对于这类改变问法的问题,一般只需将状态转移方程中的\(max\)改成\(sum\)即可。例如若每件物品均是完全背包中的物品,转移方程即为
\(F[i,v] = sum\{F[i?1,v],F[i,v?C_i]\}\)
初始条件是\(F[0,0] = 1\)。
F[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int v = 0; v <= V; ++v) {
if (v >= c[i]) F[i][v] = F[i-1][v] + F[i-1][v-c[i]];
else F[i][v] = F[i-1][v];
}
}
ans = F[n][V];
printf("%d\n", ans);
3.求装得尽量满
再看一题:装箱问题 [NOIp2001普及组第4题]
其实这里\(W_i\)就是\(C_i\)。
memset(F, 0, sizeof(F));
for (int i = 1; i <= n; ++i) {
for (int v = V; v >= c[i]; --v) {
F[v] = max(F[v], F[v-c[i]] + c[i]);
}
}
for (int i = 0; i <= V; ++i) ans = max(ans, F[i]);
printf("%d\n", V - ans);
4.求所有体积可能
又来一题:积木城堡
求出每个高度的城堡数量。
for (int i = 0; i < n; ++i) {
int np = 0;
int now;
int sum = 0;
while (1) {
scanf("%d", &now);
if (now == -1) break;
a[++np] = now;
sum += now;
}
if (max_sum < sum) max_sum = sum;
memset(F, 0, sizeof(F));
F[0] = 1;
for (int j = 1; j <= np; ++j) {
for (int v = sum; v >= a[j]; --v) {
if (F[v-a[j]] && !F[v]) {
++h[v];
F[v] = 1;
}
}
}
}
内容总结
以上是互联网集市为您收集整理的[C++]01背包问题全部内容,希望文章能够帮你解决[C++]01背包问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。