它的主要思路是假定某人拥有大量物品,重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中并加密消息。背包中的物品总重量是公开的,所有可能的物品也是公开的,但背包中的物品是保密的。附加一定的限制条件,给出重量,而要列出可能的物品,在计算上是不可实现的。背包问题是熟知的不可计算问题,背包体制以其加密,解密速度快而引人注目。但是,大多数一次背包体制均被破译了,因此很少有人使用它。
#include<iostream> using namespace std; int findM(int N,int K,int G[],int W[]) { int *M=new int[N+1],i,j,k; for(i=0;i<N+2;i++) M[i]=0; for(i=0;i<K;i++) { for(j=N;j>=G[i];j--) { for(k=1;j-k*G[i]>=0;k++) { M[j]=M[j]>k*W[i]+M[j-k*G[i]]?M[j]:k*W[i]+M[j-k*G[i]]; } } } return M[N]; } int main(){ int N,K,i; while(cin>>N>>K) { int *G=new int[K]; int *W=new int[K]; for(i=0;i<K;i++) cin>>G[i]>>W[i]; cout<<findM(N,K,G,W)<<endl; delete []G; delete []W; } return 0; }
#include<fstream> #include<iostream> usingnamespacestd; #defineMAXSIZE1000 intA[MAXSIZE+1][MAXSIZE+1],B[MAXSIZE+1][MAXSIZE+1]; intc[MAXSIZE+1],w[MAXSIZE+1]; intF(intn,intv){ if(n==0)return0; if(!A[n][v]&&v>=c[n]) A[n][v]=F(n-1,v-c[n])+w[n]; if(!B[n][v])B[n][v]=F(n-1,v); returnA[n][v]>B[n][v]?A[n][v]:B[n][v]; } intmain(intargc,char*argv[]) { intn,v; memset(A,0,sizeof(A)); memset(B,0,sizeof(B)); ifstreamin("in.txt"); ofstreamout("out.txt"); in>>n>>v; for(inti=1;i<=n;i++) in>>c[i]>>w[i]; out<<F(n,v); return0; }
var i,j,v,n:longint; f,c,w:array[0..100]oflongint; functionmax(a,b:longint):longint; begin ifa>bthenexit(a)elseexit(b); end; begin read(n,v); fillchar(f,sizeof(f),0); fori:=1tondo read(c[i],w[i]); fori:=1tondo forj:=vdowntoc[i]do f[j]:=max(f[j],f[j-c[i]]+w[i]); writeln(f[v]); end.
varm,n,x,i:integer; c,w:array[1..30]ofinteger; f:array[0..30,0..300]ofinteger; functionmax(x,y:integer):integer; begin ifx>ythenmax:=xelsemax:=y; end; begin readln(n,m); fori:=1tondo readln(c[i],w[i]); fori:=1tondo forx:=1tomdo ifx>=c[i]thenf[i,x]:=max(f[i-1,x-c[i]]+w[i],f[i-1,x]) elsef[i,x]:=f[i-1,x]; writeln(f[n,m]); end.
#include<stdio.h> #include<malloc.h> typedefstruct { intobject; intweight; intvalue; }KnapSack; KnapSack*knapsack;//背包数组,用malloc或new动态创建 intnum;//物体的个数 intcontainer;//背包的最大容量 int**array=NULL;//用来存放子问题的结果 //动态创建背包 voidCreate_KnapSack() { charc; printf("inputthenumberofobjects\n"); scanf("%d",&num); knapsack=newKnapSack[num+1]; printf("inputweightandvalueof%dobjects,like1:410\n",num); for(inti=1;i<=num;i++) { scanf("%d%c%d%c%d",&knapsack[i].object,&c,&knapsack[i].weight,&c,&knapsack[i].value); getchar();//为了获取空格或其他输入,声明下scanf挺恶心 } intk=knapsack[num].value; printf("%d",k); printf("inputthevolumeoftheknapsack:\n"); scanf("%d",&container); } //确定最优子问题 voidResolve_KnapSack() { intk=knapsack[num].value; printf("%d",k); //创建动态二维数组m[num][container] array=(int**)malloc((num+1)*sizeof(int*)); for(inti=0;i<=num;i++) array[i]=(int*)malloc((container+1)*sizeof(int)); // for(intj=0;j<=container;j++) array[num][j]=(j>=knapsack[num].weight)?knapsack[num].value:0; //子问题的最优结果 for(intm=num-1;m>0;m--) for(intn=0;n<=container;n++) if(n>knapsack[m].weight&&array[m+1][n]<=array[m+1][n-knapsack[m].weight]+knapsack[m].value) array[m][n]=array[m+1][n-knapsack[m].weight]+knapsack[m].value; //else包括两种情况,共同点是该物体没有被使用 else array[m][n]=array[m+1][n]; } //往回找,确定某个物体i是否被使用 bool*Trace_back() { intc=container; bool*used; used=(bool*)malloc(sizeof(bool)*(num+1)); for(inti=1;i<num;i++) if(array[i][c]==array[i+1][c]) used[i]=0; else { used[i]=1; c-=knapsack[i].weight; } used[num]=(c==knapsack[num].weight)?1:0; returnused; } //用来输出被使用的物体及其相关值 voidPrint_KnapSack(bool*used) { printf("theobjectsusedasfollows:\n"); for(inti=1;i<=num;i++) if(used[i]) printf("%d:%d%d\n",knapsack[i].object,knapsack[i].weight,knapsack[i].value); } voidmain() { bool*used; Create_KnapSack(); Resolve_KnapSack(); used=Trace_back(); Print_KnapSack(used); }
varp,t:array[1..10000]ofinteger; m,n:integer; min:longint; procedureinit; vari:integer; begin readln(m,n); min:=maxlongint; fori:=1tondo begin readln(p[i],t[i]); ift[i]<minthenmin:=t[i]; end; end; procedureqsort(l,r:integer); vari,j,x,temp:longint; begin i:=l; j:=r; x:=t[(l+r)div2]; whilei<jdo begin while(i<j)and(t[i]<x)doinc(i); while(i<j)and(x<t[j])dodec(j); ifi<=jthen begin temp:=t[i]; t[i]:=t[j]; t[j]:=temp; temp:=p[i]; p[i]:=p[j]; p[j]:=temp; inc(i); dec(j); end; end; ifi<rthenqsort(i,r); ifl<jthenqsort(l,j); end; functionmax(a,b:longint):longint; begin ifa>bthenmax:=aelsemax:=b; end; procedurework; varf:array[0..10000]oflongint; i,j:longint; begin fillchar(f,sizeof(f),0); fori:=mintomdo begin f[i]:=f[i-1]; forj:=1tondo ifi-t[j]>=0thenf[i]:=max(f[i],f[i-t[j]]+p[j])elsebreak; end; writeln(f[m]); end; begin init; qsort(1,n); work; end.
var i,j,v,n:longint; f,c,w:array[0..100]oflongint; functionmax(a,b:longint):longint; begin ifa>bthenexit(a)elseexit(b); end; begin read(n,v); fillchar(f,sizeof(f),0); fori:=1tondo read(c[i],w[i]); fori:=1tondo forj:=c[i]tovdo f[j]:=max(f[j],f[j-c[i]]+w[i]); writeln(f[v]); end.