一个物品集S，如果有S的一个子集S',S'的元素和为C，我就称物品集S可以达到背包大小C。
现在用一个标记数组int flag[MAXC+1];来标记能达到的背包大小，
我们先考虑物品集为空的情况，在一个个地把S的元素加入考虑的物品集
那么开始时，flag[0]=1,flag[i]=0,0<i<=MAXC
然后将一个物品加入考虑中，可以用原来的flag[]生成新的flag[]
如果要生成最优值，可以用flag[]记录这个解是在添加哪个物品的时候得到的。
程序代码：
#include <iostream>
using namespace std;
//int* a ,int n 表示n个物品的物品集
//int C 是背包的大小
//int* x,int& xn 通过这个两个参数返回一个最优解，这里x[]表示达到最优值你要取哪些物品
//return 最优值
const int MAXC=100000;
int knapsackx(int* a,int n,int C,int* x,int & xn)
{
static int flag[MAXC+1];
fill(flag,flag+C+1,-1);
flag[0]=INT_MAX;//大小为0是可以达到的，但没有取任何物品，我就随便赋了一个INT_MAX
for(int i=0;i<n;i++){
for(int j=0;j<=C;j++){
if(flag[j]!=-1 && flag[j]!=i && j+a[i]<=C && flag[j+a[i]]==-1){
flag[j+a[i]]=i;
}
}
}
//取得最优值
int best;
for(best=C;flag[best]==-1;best--);
//生成最优解
xn=0;
int r=best;
while(r){
x[xn++]=flag[r];
r-=a[flag[r]];
}
//将x[]翻转
for(int i=0;i<xn/2;i++){
swap(x[i],x[xn-1-i]);
}
return best;
}
int main()
{
int a[]={1,3,5,7,4};
int x[10],xn;
int best=knapsackx(a,5,14,x,xn);
printf("最优值=%d\n",best);
printf("可以取如下编号的物品来达到最优值:");
for(int i=0;i<xn;i++){
printf("%d ",x[i]);
}
printf("\n");
system("pause");
}
[[it] 本帖最后由 leeco 于 2008-4-30 19:19 编辑 [/it]]
2008-04-30 18:18
