/********************************************************
** Highlight software by yzfy(雨中飞燕) http:// *
*********************************************************/
#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");
}
