动态规划
- // 求解 0_1 背包问题
- // 动态规划
- #include<stdio.h>
- #define MaxN 20
- #define MaxW 100
- int knap(int f[MaxN][MaxW],int w[],int v[],int W,int n){
- // 动态规划求数组 f[][]
- int i,r;
- for(i=0;i<=n;i++)
- f[i][0] = 0;
- for(r=0;r<=W;r++)
- f[0][r] = 0;
- for(i=1;i<=n;i++){
- for(r=1;r<=W;r++){
- if(r <w[i])
- f[i][r] = f[i-1][r];
- else{
- if(f[i-1][r] < f[i-1][r-w[i]] + v[i])
- f[i][r] = f[i-1][r-w[i]] + v[i];
- else
- f[i][r] = f[i-1][r];
- }
- }
- }
- return f[n][W];
- }
- int Traceback(int f[MaxN][MaxW],int w[],int x[],int W,int n){
- int i,r=W;
- int maxw = 0;
- for(i=n;i>0;i--){
- if(f[i][r] != f[i-1][r]){
- x[i] = 1;
- maxw += w[i];
- r = r - maxw;
- }
- else
- x[i] = 0;
- }
- return maxw;
- }
- void dispknap(int x[],int maxw,int maxv,int n){
- int i;
- printf("最佳背包方案是:\n");
- for(i=0;i<=n;i++){
- if(x[i] == 1)
- printf("选取第 %d 种物品 \ n",i);
- }
- printf("总重量 =%d, 总价值 =%d",maxw,maxv);
- }
- int main(){
- int f[MaxN][MaxW];
- int x[MaxN];
- int maxv;
- int maxw;
- int n=5,W=10;
- int w[MaxN] = {0,2,2,6,5,4};
- int v[MaxN] = {0,6,3,5,4,6};
- maxv = knap(f,w,v,W,n);
- maxw = Traceback(f,w,x,W,n);
- dispknap(x,maxw,maxv,n);
- return 0;
- }
回溯法
- #include<stdio.h>
- #define MAXN 20
- int maxw;
- int maxv;
- int x[MAXN];
- void knap(int w[],int v[],int W,int n,int i,int tw,int tv,int op[]){
- int j;
- if(i>n){
- if(tw<W && tv>maxv){
- maxv = tv;
- maxw = tw;
- for(j=1;j<=n;j++)
- x[j] = op[j];
- }
- }
- else{
- op[i] = 1;
- knap(w,v,W,n,i+1,tw+w[i],tv+v[i],op);
- op[i] = 0;
- knap(w,v,W,n,i+1,tw,tv,op);
- }
- }
- void disp(int x[],int n){
- int i;
- printf("最佳方案是:\n");
- for(i=1;i<=n;i++){
- if(x[i] == 1)
- printf("选取第 %d 个物品 \ n",i);
- }
- printf("总重量 = %d, 总价值 = %d",maxw,maxv);
- }
- int main(){
- int n=4;
- int W = 7;
- int op[MAXN];
- int w[] = {0,5,3,2,1};
- int v[] = {0,4,4,3,1};
- knap(w,v,W,n,1,0,0,op);
- disp(x,n);
- return 0;
- }
左剪枝
- void knap(int w[],int v[],int W,int n,int i,int tw,int tv,int op[]){
- int j;
- if(i>n){
- if(tw<W && tv>maxv){
- maxv = tv;
- maxw = tw;
- for(j=1;j<=n;j++)
- x[j] = op[j];
- }
- }
- else{
- if(tw+w[i] <W)
- {
- op[i] = 1;
- knap(w,v,W,n,i+1,tw+w[i],tv+v[i],op);
- }
- op[i] = 0;
- knap(w,v,W,n,i+1,tw,tv,op);
- }
- }
右剪枝
- void knap(int w[],int v[],int W,int n,int i,int tw,int tv,int op[]){
- int j,m;
- if(i>n){
- if(tw<W && tv>maxv){
- maxv = tv;
- maxw = tw;
- for(j=1;j<=n;j++)
- x[j] = op[j];
- }
- }
- else{
- if(tw+w[i] < W)
- {
- op[i] = 1;
- knap(w,v,W,n,i+1,tw+w[i],tv+v[i],op);
- }
- op[i] = 0;
- m=0;
- for(j=0;j<i;j++)
- if(op[j] == 0) m++;
- if(m<=1)
- knap(w,v,W,n,i+1,tw,tv,op);
- }
- }
来源: http://www.bubuko.com/infodetail-3364779.html