0-1背包
0-1背包
问题描述： 给定n种物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品（物品不能分割），使得装入背包中物品的总价值最大? 抽象描述： x[n]:表示物品的选择，x[i]=1表示选择放进物品i到背包中。
问题分析： 1.抽象之后背包问题转换为找到一个最优的数组，x1，x2，.....,xn的0-1序列。 2.假设最优解的序列为x1，x2，.....,xn，能使背包容量C的总价值最大. 如果，x1=1，则x2,...,xn是C-w1容量的背包的总价值依然是 最大的序列； 如果，x1=0，则x2,....,xn是C容量的背包的总价值依然是 最大的序列。 这就是我们所说的最优子结构性质。 3.进一步分析：我们用m(i,j)表示为已经判断好了i:n的序列的背包最大价值，并且此时的背包剩余的容量为j，对物品i进行判断 如果j>wi, 就只要做出选择wi和不选择wi情况下，哪种更能使背包的总价值更大：m(i,j)=max{ m(i+1,j),m(i+1,j-wi)+vi}(注意这是个递归式) 如果j<wi: m(i,j)=m(i+1,j) 初始化： m(n,j)=vn (j>= wn)； m(n,j)=0 (0<=j< wn) m(0,C)=0 最终的结果：m(1,C) 4.依次我们就得到了一个递归的表达式：
5.如果单纯的从利用递归，重复计算了很多的值，耗费的时间是很大的，动态规划还需避免这种重复计算，怎样自顶向下或自底向上的计算呢？ 采用列表的方法就可以很好的分析设计自顶向下或自底向上的计算的算法了 举例分析： n=3,c=6,w={4,3,2} v={5,2,1} m[i][j]=max{ m[i+1][j], m[i+1][j-w[i]]+v[i] } 列表如下：
最左边箭头：我们计算的方向，从第3行开始向上计算法值。 表中红色箭头是我们通过选择做出的结果：列如 m[2][3]=max{m[3][3],m[3][3-w[2]]+v[2]}，我们最终选择了m[3][3-w[2]]+v[2]。 整个问题的最优解保存在m[1][6]中。
#include <iostream>
#include <vector>
using namespace std;
int maxPrice(int n, int c, vector<int> vecw, vector<int> vecp);
int main()
{
//物品的数量和背包的容量
int n, c, weight, price;
//获得n个物体的重量和价值，n，c都为0的时候结束
cin >> n >> c;
while( n != 0 && c != 0 )
{
// 物品的重量vecw和物体的价值vecp
vector<int> vecw, vecp;
for (int i = 0; i < n; ++i)
{
cin >> weight;
vecw.push_back(weight);
}
for (int j = 0; j < n; ++j)
{
cin >> price;
vecp.push_back(price);
}
//找到价值的最大值
int max_Price = maxPrice(n, c, vecw, vecp);
cout << max_Price << endl;
cin >> n >> c;
}
return 0;
}
int maxPrice(int n, int c, vector<int> vecw, vector<int> vecp)
{
int price = 0, flag = 0;
if (c == 0)
return 0;
for(int l = 0; l < n; ++l)//测试是否有能装入包中的数据
if (vecw[l] < c)
{
flag = 1;
break;
}
if (flag == 0) //如果没有能装入包中的数据就返回 0
return 0;
for(int i = 0; i < n; ++i)
{
int weight = c;
weight -= vecw[i];
if (weight >= 0)
{
vector<int> vec_w, vec_p;
for (int j= 0; j < n; ++j)
if ( i != j)//创建一个新的数组存储下一组数据
{
vec_w.push_back(vecw[j]);
vec_p.push_back(vecp[j]);
}
int current = vecp[i] + maxPrice(n-1, weight, vec_w, vec_p);//递归求最大值
if ( price < current)
price = current;
}
}
return price;
}运行结果：
