Scribd Logo
Upload

Welcome to Scribd!

  • 34 views

    Knapsack

    Uploaded by

    Sabarish Kuduwa
    The document describes an algorithm to solve the knapsack problem using backtracking. It defines profit and weight arrays, initializes variables to track the maximum profit and weight. It includes functions to calculate bounds and recursively try adding items to the knapsack. The main function runs the backtracking algorithm, prints the selected items and outputs the final profit and weight within the knapsack capacity limit.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    Knapsack

    Uploaded by

    Sabarish Kuduwa
    34 views3 pages
    The document describes an algorithm to solve the knapsack problem using backtracking. It defines profit and weight arrays, initializes variables to track the maximum profit and weight. It includes functions to calculate bounds and recursively try adding items to the knapsack. The main function runs the backtracking algorithm, prints the selected items and outputs the final profit and weight within the knapsack capacity limit.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes an algorithm to solve the knapsack problem using backtracking. It defines profit and weight arrays, initializes variables to track the maximum profit and weight. It includes functions to calculate bounds and recursively try adding items to the knapsack. The main function runs the backtracking algorithm, prints the selected items and outputs the final profit and weight within the knapsack capacity limit.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    34 views3 pages

    Knapsack

    Uploaded by

    Sabarish Kuduwa
    The document describes an algorithm to solve the knapsack problem using backtracking. It defines profit and weight arrays, initializes variables to track the maximum profit and weight. It includes functions to calculate bounds and recursively try adding items to the knapsack. The main function runs the backtracking algorithm, prints the selected items and outputs the final profit and weight within the knapsack capacity limit.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    You are on page 1of 3

    CODING: REG.

    NO:41909112029

    KNAPSACK PROBLEM

    #include<stdio.h>
    #include<conio.h>

    float final_profit=-1.0;
    int p[9]={0,11,21,31,33,43,53,55,65};
    int w[9]={0,1,11,21,23,33,43,45,55};
    int m=110,n=8;
    int temp[9],x[9];
    float final_wt=-1.0;

    float bound_calculation(int cp,int cw,int k)


    {
    int ub,c,i;
    ub=cp;
    c=cw;
    for(i=k+1;i<=n;++i)
    {
    c=c+w[i];
    if(c<m)
    ub=ub+p[i];
    else
    return(ub+(1-(c-m)/w[i])*p[i]);
    }
    return ub;
    }

    void bk(int k,int cp,int cw)


    {
    int new_k,new_cp,new_cw,j;
    if(cw+w[k]<=m)
    {
    temp[k]=1;
    if(k<n)
    {
    new_k=k+1;
    new_cp=cp+p[k];
    new_cw=cw+w[k];
    bk(new_k,new_cp,new_cw);
    }
    if((new_cp>final_profit)&&(k==n))
    {
    final_profit=new_cp;
    final_wt=new_cw;
    for(j=1;j<=k;++j)
    x[j]=temp[j];
    }
    }
    if(bound_calculation(cp,cw,k)>=final_profit)
    {
    temp[k]=0;
    if(k<n)
    bk(k+1,cp,cw);
    if((cp>final_profit)&&(k==n))
    {
    final_profit=cp;
    final_wt=cw;
    for(j=1;j<=n;++j)
    x[j]=temp[j];
    }
    }
    }

    void main()
    {
    int i;
    clrscr();
    printf("\n \t Knapsack problem using back tracking algorithm");
    printf("\nCapacity of knapsack:%d",m);
    printf("\n\nProfit \t Weight");
    printf("\n----------------------------");
    for(i=1;i<=n;++i)
    printf("\n%d\t%d",p[i],w[i]);
    printf("\n----------------------------");
    bk(1,0,0);
    printf("\n Following items are selected from knapsack");
    for(i=1;i<=n;++i)
    {
    if(x[i]==1)
    printf("\n\t\titem%d",i);
    }
    printf("\n Final weight:%0.2f",final_wt);
    printf("\n Final profit:%0.2f",final_profit);
    getch();
    }
    OUTPUT:

    Knapsack problem using back tracking algorithm

    Capacity of knapsack:110

    Profit Weight
    --------------------
    11 1
    21 11
    31 21
    33 23
    43 33
    53 43
    55 45
    65 55
    ----------------------------

    Following items are selected from knapsack


    item1
    item2
    item3
    item5
    item6

    Final weight:109.00

    Final profit:159.00

    RESULT:

    You might also like