关于背包问题的题目,前人之述备矣,这里只讨论实现
输入:
n
ca
w_1 v_1
w_2 v_2
...
w_n v_n
其中,n是物品总数,ca是背包大小,w_n是第n个物品的重量,v_n是第n个物品的价值
输出:
v_1 x
v_2 x
v_3 x
...
其中,v_n是当前情况为x时背包的价值,x是一串序列,由0,1组成,表示是否放入背包
如: 1001就表示第一个和最后一个物品放入背包,中间两个物品不放入
要求编写一个程序,输出所有可满足解.
思路很简单,就是穷举.穷举每一个情况.
伪代码如下:
f() {
if (没有可以放进背包的东西) {
输出
} else {
放进背包
f()
不放进背包
f()
恢复原状
}
}
这样,就构造了一个二叉树,可以输出每一种可选解的情况.
我的代码如下:
#include <iostream>
#include <functional> struct Pack {
unsigned cnt;
unsigned *w; // weights
unsigned *v; // values
unsigned *x; // put in or not
unsigned ca; // capacity Pack(unsigned items_cnt) : cnt(items_cnt) {
w = new unsigned [items_cnt];
v = new unsigned [items_cnt];
x = new unsigned [items_cnt]; for (int i = ; i < items_cnt; ++i) {
w[i] = v[i] = x[i] = -;
}
} ~Pack() {
delete [] w;
delete [] v;
delete [] x;
}
}; int main() {
unsigned c; std::cin >> c; Pack p(c); std::cin >> p.ca; for (int i = ; i < p.cnt; ++i) {
std::cin >> p.w[i] >> p.v[i];
} std::function<unsigned()> totval = [&]() {
unsigned cnt = ; for (int i = ; i < p.ca; ++i) {
if (p.x[i] == ) cnt += p.v[i];
} return cnt;
}; std::function<unsigned()> totwt = [&]() {
unsigned cnt = ; for (int i = ; i < p.ca; ++i) {
if (p.x[i] == ) cnt += p.w[i];
} return cnt;
}; std::function<void()> loop = [&]() {
unsigned no = -;
for (int i = ; i < p.cnt; ++i) {
if (p.x[i] == -) {
no = i;
break;
}
} if (no == -) {
std::cout << totval() << ' ';
for (int i = ; i < p.cnt; ++i) {
std::cout << p.x[i];
}
std::cout << std::endl;
} else {
p.x[no] = ;
loop(); p.x[no] = ; if (totwt() <= p.ca) {
loop();
} p.x[no] = -;
}
}; loop(); return ;
}
测试数据:
输出:
可以找到最优解,10101.