第1个回答 2008-11-15
题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。
过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
有了这个过程以后，01背包问题的伪代码就可以这样写：
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的细节问题
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
前面的伪代码中有 for v=V..1，可以将这个循环的下限进行改进。
由于只需要最后f[v]的值，倒推前一个物品，其实只要知道f[v-w[n]]即可。以此类推，对以第j个背包，其实只需要知道到f[v-sum{w[j..n]}]即可，即代码中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
这对于V比较大时是有用的。
#include<fstream>
using namespace std;
struct bag{
double w;
double p;
double p_w;
int order;
}; //说明物品特性
void sort(struct bag *a,int low,int high);
int main()
{
int n,i;
double *x;
double m,cost=0;
struct bag *b; //结构数组，用于表示所有物品
//定义文件流并与具体的磁盘文件相关联
ifstream fin;
fin.open("背包问题_in.txt");
ofstream fout;
fout.open("背包问题_out.txt");
//输入物品数目 n 背包容量 M
fin>>n>>m;
//动态分配存储空间
b=new struct bag[n];
x=new double[n];
for(i=0;i<n;i++){
fin>>b[i].w>>b[i].p; //输入物品重量和运价
b[i].p_w=b[i].p/b[i].w; //求出运价重量比
b[i].order=i; //贴标签
}
sort(b,0,n-1); //按运价重量比从大到小进行排序
for(i=0;i<n;i++)
x[i]=0; //初始化解向量
for(i=0;i<n;i++) //处理所有物品
if(b[i].w<=m){ //若背包能放得下整个物品
x[b[i].order]=1; //放入背包
m-=b[i].w; //背包剩余容量减小
cost+=b[i].p; //总价值增加
}
else{ //否则，放不下整个物品
x[b[i].order]=m/b[i].w; //放一部分
cost+=x[b[i].order]*b[i].p; //总价值增加
break; //打断，后续物品由于不能放入背包，不需处理
}
for(i=0;i<n;i++)
fout<<x[i]<<"\t"; //输出解向量
fout<<endl<<cost;
//删除动态分配下的空间
delete []x;
delete []b;
//关闭文件指针
fin.close();
fout.close();
return 0;
}
int par(struct bag *a,int low,int high)
{
struct bag temp;
temp=a[low];
double t;
t=a[low].p_w;
while(low<high){
while(low<high && a[high].p_w<=t)
--high;
a[low]=a[high];
while(low<high && a[low].p_w>=t)
++low;
a[high]=a[low];
}
a[low]=temp;
return low;
}
void sort(struct bag *a,int low,int high)
{
int loc;
if(low<high){
loc=par(a,low,high);
sort(a,low,loc-1);
sort(a,loc+1,high);
}
}
第2个回答 2008-11-23
上面的都太麻烦太多太难看了~~~
#define SIZE 4
void try(int i,int n,int weight[],int value[],int weightLimit,int solution[],int bestSolution[]);
void saveSolution(int solution[],int bestSolution[],int size);
int getWeight(int solution[],int weight[],int size);
int getValue(int solution[],int value[],int size);
void printSolution(int solution[],int size);
main()
{
int i,weightLimit=50;
int solution[SIZE+1]={0};
int bestSolution[SIZE+1]={0};
int weight[SIZE+1]={0,16,15,15,20};
int value[SIZE+1]={0,45,25,25,30};
try(1,SIZE,weight,value,weightLimit,solution,bestSolution);
for(i=1;i<=SIZE;i++)
printf("%d\t",bestSolution[i]);
system("pause");
return 0;
}
void try(int i,int n,int weight[],int value[],int weightLimit,int solution[],int bestSolution[])
{
int xi;
for(xi=0;xi<=1;xi++){
solution[i]=xi;
if (getWeight(solution,weight,n)<=weightLimit){
if(i==n){//求一元组，不再递归
//printSolution(bestSolution,n);
if(getValue(solution,value,n)>getValue(bestSolution,value,n))
saveSolution(solution,bestSolution,n);//将当前方案作为最大值方案
}
else
try(i+1,n,weight,value,weightLimit,solution,bestSolution);
}
solution[i]=0;
}
}
void saveSolution(int solution[],int bestSolution[],int size)
{
int i;
for(i=1;i<=size;i++)
bestSolution[i]=solution[i];
}
int getWeight(int solution[],int weight[],int size)
{
int totalWeight=0,i;
for(i=1;i<=size;i++)
totalWeight+=solution[i]*weight[i];
return totalWeight;
}
int getValue(int solution[],int value[],int size)
{
int totalValue=0,i;
for(i=1;i<=SIZE;i++)
totalValue+=solution[i]*value[i];
return totalValue;
}
void printSolution(int solution[],int size)
{
int i;
for(i=1;i<=size;i++)
printf("%2d",solution[i]);
printf("\n");
}