众文网1.背包问题的算法
1）登上算法 用登山算法求解背包问题 function []=DengShan(n,G,P,W) %n是背包的个数，G是背包的总容量，P是价值向量，W是物体的重量向量 %n=3;G=20;P=[25,24,15];W2=[18,15,10]；%输入量 W2=W; [Y,I]=sort(-P./W2);W1=[];X=[];X1=[]; for i=1:length(I) W1(i)=W2(I(i)); end W=W1; for i=1:n X(i)=0; RES=G；%背包的剩余容量 j=1; while W(j) 时间复杂度是非指数的2）递归法 先看完全背包问题 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1,W2,。
,Wn， 每件的价值分别为C1,C2,。,Cn.若的每种物品的件数足够多. 求旅行者能获得的最大总价值。
本问题的数学模型如下： 设 f(x)表示重量不超过x公斤的最大价值， 则 f(x)=max{f(x-i)+c[i]} 当x>=w[i] 1可使用递归法解决问题程序如下： program knapsack04; const maxm=200;maxn=30; type ar=array[0..maxn] of integer; var m,n,j,i,t:integer; c,w:ar; function f(x:integer):integer; var i,t,m:integer; begin if x=0 then f:=0 else begin t:=-1; for i:=1 to n do begin if x>=w[i] then m:=f(x-i)+c[i]; if m>t then t:=m; end; f:=t; end; end; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); writeln(f(m)); end. 说明：当m不大时，编程很简单，但当m较大时，容易超时. 4.2 改进的递归法 改进的的递归法的思想还是以空间换时间，这只要将递归函数计算过程中的各个子函数的值保存起来，开辟一个 一维数组即可 程序如下： program knapsack04; const maxm=2000;maxn=30; type ar=array[0..maxn] of integer; var m,n,j,i,t:integer; c,w:ar; p:array[0..maxm] of integer; function f(x:integer):integer; var i,t,m:integer; begin if p[x]-1 then f:=p[x] else begin if x=0 then p[x]:=0 else begin t:=-1; for i:=1 to n do begin if x>=w[i] then m:=f(i-w[i])+c[i]; if m>t then t:=m; end; p[x]:=t; end; f:=p[x]; end; end; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); fillchar(p,sizeof(p),-1); writeln(f(m)); end.3）贪婪算法 改进的背包问题：给定一个超递增序列和一个背包的容量，然后在超递增序列中选（只能选一次）或不选每一个数值，使得选中的数值的和正好等于背包的容量。代码思路：从最大的元素开始遍历超递增序列中的每个元素，若背包还有大于或等于当前元素值的空间，则放入，然后继续判断下一个元素；若背包剩余空间小于当前元素值，则判断下一个元素 简单模拟如下：#define K 10#define N 10 #i nclude #i nclude void create(long array[],int n,int k) {/*产生超递增序列*/ int i,j; array[0]=1; for(i=1;i { long t=0; for(j=0;j t=t+array[j]; array[i]=t+random(k)+1; } } void output(long array[],int n) {/*输出当前的超递增序列*/ int i; for(i=0;i { if(i%5==0) printf("\n"); printf("%14ld",array[i]); } } void beibao(long array[],int cankao[],long value,int count) {/*背包问题求解*/ int i; long r=value; for(i=count-1;i>=0;i--)/*遍历超递增序列中的每个元素*/ { if(r>=array[i])/*如果当前元素还可以放入背包，即背包剩余空间还大于当前元素*/ { r=r-array[i]; cankao[i]=1; } else/*背包剩余空间小于当前元素值*/ cankao[i]=0; } } void main() { long array[N]; int cankao[N]={0}; int i; long value,value1=0; clrscr(); create(array,N,K); output(array,N); printf("\nInput the value of beibao:\n"); scanf("%ld",&value); beibao(array,cankao,value,N); for(i=0;i if(cankao[i]==1) value1+=array[i]; if(value==value1) { printf("\nWe have got a solution,that is:\n"); for(i=0;i if(cankao[i]==1) { if(i%5==0) printf("\n"); printf("%13ld",array[i]); } } else printf("\nSorry.We have not got a solution.\n")； } 贪婪算法的另一种写法，beibao函数是以前的代码，用来比较两种算法：#define K 10#define N 10 #i nclude #i nclude void create(long array[],int n,int k) { int i,j; array[0]=1; for(i=1;i { long t=0; for(j=0;j t=t+array[j]; array[i]=t+random(k)+1; } } void output(long array[],int n) { int i; for(i=0;i { if(i%5==0) printf("\n"); printf("%14ld",array[i]); } } void beibao(long array[],int cankao[],long value,int count) { int i; long r=value; for(i=count-1;i>=0;i--) { if(r>=array[i]) { r=r-array[i]; cankao[i]=1; } else cankao[i]=0; } } int beibao1(long array[],int cankao[],long value,int n) {/*贪婪算法*/ int i; long value1=0; for(i=n-1;i>=0;i--)/*先放大的物体，再考虑小的物体*/ if((value1+array[i]) { cankao[i]=1;/*1表示放入*/ value1+=array[i]；/*背包剩余容量减少*/ } else cankao[i]=0; if(value1==value) return 1; return 0; } void main() { long array[N]; int cankao[N]={0}; int cankao1[N]={0}; int i; long value,value1=0; clrscr(); create(array,N,K); output(array,N); printf("\nInput the value of beibao:\n"); scanf("%ld",&value); beibao(array,cankao,value,N); for(i=0;i if(cankao[i]==1) value1+=array[i]; if(value==value1) { printf("\nWe have got a solution,that is:\n"); for(i=0;i if(cankao[i]==1) { if(i%5==0) printf("\n"); printf("%13ld",array[i]); } } else printf("\nSorry.We have not got a solution.\n"); printf("\nSecond method:\n"); if(beibao1(array,cankao1,value,N)==1) { for(i=0;i if(cankao1[i]==1) { if(i%5==0) printf("\n"); printf("%13ld",array[i]); } } else 。
2.什么是背包算法啊?可以说的详细一点吗?谢谢大家了```
该算法是根据数学上的背包问题设计的。背包问题是一个最优化问题，即对一个给定空间或负重的背包和许多大小不一的物体，哪些物体放入背包才能使得浪费的背包空间或负重最小？在背包很小和物体数目较少时，这个问题还比较容易解决；但当背包很大且有很多个物体时，问题的求解就十分困难。通常，这个问题会有一个或者多个解，也有可能根本没有解。
1977年，Merkle与Hellman合作设计了使用背包问题实现信息加密的方法。其工作原理是：假定甲想加密，则先产生一个较易求解的背包问题，并用它的解作为专用密钥；然后从这个问题出发，生成另一个难解的背包问题，并作为公共密钥。如果乙想向甲发送报文，乙就可以使用难解的背包问题对报文进行加密，由于这个问题十分难解，所以一般没有人能够破译密文；甲收到密文后，可以使用易解的专用密钥解密。
该算法提出以后，经过多年的探讨和研究，最终发现了它的一个致命错误，使之失去了任何保密的实用价值。
3.求解背包问题算法的设计与实现
这个不像是背包问题，这是求从一个集合内找个所有子集合，然后其和等于给定值的。
这个可以用回溯做.
如下面程序：
#include<stdio.h>
#define N 100
int weight[N]；//物品重量
int n；//物品总数
int visit[N]；//用了哪些物品，为了输出
int total；//需要的重量
void solve(int p,int data,int num)
//p表示开始查找的坐标，data表示当前的重量 。num表示找到的个数。
{
int i;
//找到一个解
if(data==total)
{
for(i=0;i<num;i++) printf("%d ",visit[i]);
printf("\n");
return ;
}
for(i=p;i<n;i++)
{
if(weight[i]+data<=total)
{
visit[num]=weight[i];
solve(i+1,data+weight[i],num+1);
}
}
}
int main()
{
int i;
scanf("%d",&n)；//输入个数
for(i=0;i<n;i++) scanf("%d",&weight[i])；//输入值。
scanf("%d",&total)；//要查找的数。
solve(0,0,0)；//查找。
return 0;
}
4.背包算法的使用
program p;var v,w,m:array[1..100] of integer; i,j,n,t,s,z:integer;begin write('input n:'); readln(n); for i:=1 to n do begin write('input v:'); readln(v[i]); write('input w:'); readln(w[i]); m[i]:=i; end; write('input s:'); readln(s); for i:=1 to n-1 do for j:=i+1 to n do if v[i] div w[i] 一.动态规划求解0-1背包问题 /************************************************************************/ /* 0-1背包问题： /* 给定n种物品和一个背包 /* 物品i的重量为wi，其价值为vi /* 背包的容量为c /* 应如何选择装入背包的物品，使得装入背包中的物品 /* 的总价值最大？ /* 注：在选择装入背包的物品时，对物品i只有两种选择， /* 即装入或不装入背包。 不能将物品i装入多次，也 /* 不能只装入部分的物品i。 /* /* 1. 0-1背包问题的形式化描述： /* 给定c>0, wi>0, vi>0, 0<=i<=n，要求找到一个n元的 /* 0-1向量（x1, x2, 。 , xn）， 使得： /* max sum_{i=1 to n} (vi*xi)，且满足如下约束： /* （1） sum_{i=1 to n} (wi*xi) <= c /* (2) xi∈{0, 1}, 1<=i<=n /* /* 2. 0-1背包问题的求解 /* 0-1背包问题具有最优子结构性质和子问题重叠性质，适于 /* 采用动态规划方法求解 /* /* 2.1 最优子结构性质 /* 设（y1,y2,。,yn）是给定0-1背包问题的一个最优解，则必有 /* 结论，（y2,y3,。 ,yn）是如下子问题的一个最优解： /* max sum_{i=2 to n} (vi*xi) /* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1 /* (2) xi∈{0, 1}, 2<=i<=n /* 因为如若不然，则该子问题存在一个最优解（z2,z3,。,zn）， /* 而（y2,y3,。 ,yn）不是其最优解。那么有： /* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi) /* 且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c /* 进一步有： /* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi) /* w1*y1 + sum_{i=2 to n} (wi*zi) <= c /* 这说明：（y1,z2,z3,。 zn）是所给0-1背包问题的更优解，那么 /* 说明（y1,y2,。,yn）不是问题的最优解，与前提矛盾，所以最优 /* 子结构性质成立。 /* /* 2.2 子问题重叠性质 /* 设所给0-1背包问题的子问题 P(i,j)为： /* max sum_{k=i to n} (vk*xk) /* (1) sum_{k=i to n} (wk*xk) <= j /* (2) xk∈{0, 1}, i<=k<=n /* 问题P(i,j)是背包容量为j、可选物品为i,i+1,。,n时的子问题 /* 设m(i,j)是子问题P(i,j)的最优值，即最大总价值。 则根据最优 /* 子结构性质，可以建立m(i,j)的递归式： /* a. 递归初始 m(n,j) /* //背包容量为j、可选物品只有n，若背包容量j大于物品n的 /* //重量，则直接装入；否则无法装入。 /* m(n,j) = vn, j>=wn /* m(n,j) = 0, 0<=j ,n /* //如果背包容量j 该算法存在问题： 1）.不能保证求得的最后解是最佳的； 2）.不能用来求最大或最小解问题； 3）.只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 2.例题分析 1）.[背包问题]有一个背包，背包容量是M=150。 有7个物品，物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150) (1)根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ （2）每次挑选所占空间最小的物品装入是否能得到最优解？ （3）每次选取单位容量价值最大的物品，成为解本题的策略。 <程序代码：>（环境：c++） #include 背包问题 有一个箱子容量为V，同时有n个物品，每个物品有一个体积（正整数）。设计一个算法在n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 动态规划 C#版算法 //体积表：当不同的参照物时，在各种体积箱子下，最大的占用体积 static int[,] vols = new int[100, 100]; /// /// 取若干个装入箱内，使箱子的剩余空间为最小。 /// /// 箱子的容量 /// 所有的物品 /// 剩下的容量 static int Package(int cap, int[] objects) { int count = objects.Length; if (count == 0) return cap; int i, j; for (i = 0; i vols[i - 1, j]) { vols[i, j] = objects[i] + vols[i - 1, j - objects[i]]; } else { vols[i, j] = vols[i - 1, j]; } } else { vols[i, j] = vols[i - 1, j]; } } } return cap - vols[count, cap]; } 问题描述： 给定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)表示为已经判断好了1:i-1的序列的背包最大价值，并且此时的背包剩余的容量为j，对物品i进行判断 如果j>wi，就只要做出选择wi和不选择wi情况下，哪种更能使背包的总价值更大：m(i,j)=max{m(i+1,j),m(i+1,j-wi)+vi}（注意这是个递归式） 如果j=wn); m(n,j)=0 (0。 转载请注明出处众文网 » 毕业论文背包算法(背包问题的算法)5.0
6.背包算法的C#代码
7.背包问题伪多项式算法是什么意思