fork download
copy 
  1. // ASSIGNMENT-6  Question-2   ID:201601084      Patel Kshitij
  2. //It is a CPP file..... change extention from .txt to .cpp
  3. //NOTE: 1. This question takes huffman bit-length as input (which works as weight for 01 knapsack), as mentioned in question
  4. //      2. Huffman code is available from a different company(as mentioned in question),... so that it gives bit-length for items
  5. //         corresponding to it's frequencies............(here, it is directly taken as input(step 1))
  6. //      3. W in the main program, is length of the invoice file(used for looting items), which works as knapsack capacity
  7. //      4. unbounded Knapsack is used because as mentioned in question, we can loot any number(infinite stock of item is available)
  8. //         of any item,....(clearly mentioned in question that: quantity of item is not fixed, we have full stock available)
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11.  
  12.  
  13. int unboundedKnapsack(int W, int n, int val[], int wt[])          //see step 4 in above comments
  14. {
  15.     // dp[i] is going to store maximum value
  16.     // with knapsack capacity i.
  17.     int dp[W+1];
  18.     memset(dp, 0, sizeof dp);
  19.  
  20.     int ans = 0;
  21.  
  22.     // Fill dp[] using above recursive formula
  23.     for (int i=0; i<=W; i++)
  24.       for (int j=0; j<n; j++)
  25.          if (wt[j] <= i)
  26.             dp[i] = max(dp[i], dp[i-wt[j]]+val[j]);
  27.  
  28.     return dp[W];
  29. }
  30. void sort(char *item, int *wt, int *val, int n){    //sorting function for arranging values in decreasing order...
  31.     int i,j;                                        //of value/weight ......
  32.     for(i=0;i<n;i++){
  33.         for(j=0;j<n-i-1;j++){
  34.             if((double)val[j]/wt[j]<(double)val[j+1]/wt[j+1]){
  35.                 int v=val[j],w=wt[j];
  36.                 char c=item[j];
  37.                 val[j]=val[j+1]; wt[j]=wt[j+1];item[j]=item[j+1];
  38.                 val[j+1]=v,wt[j+1]=w,item[j+1]=c;
  39.             }
  40.         }
  41.     }
  42. }
  43.  
  44. int main()
  45. {
  46.     char item[] = { 'a', 'b', 'c', 'd', 'e', 'f' };   //items
  47.     int huffman_len[]={4,4,3,3,3,1};                //corresponding bit-length lengths(works as weights for 01 knapsack)
  48.     int fin_val[]={15,25,12,25,1,15};               //values corresponding to items
  49.     int size = sizeof(item) / sizeof(item[0]);
  50.     int W=13;                                      //It is bit-length of invoice file
  51.  
  52.  
  53. 	//for(int i=0;i<6;i++) printf("item=%c len=%d fin_val=%d\n",item[i],huffman_len[i],fin_val[i]);
  54.     sort(item,huffman_len,fin_val,size);
  55.     //printf("\nAfter sorting in decreasing order of val/wt\n");
  56.     //for(int i=0;i<6;i++) printf("item=%c len=%d fin_val=%d\n",item[i],huffman_len[i],fin_val[i]);
  57.     printf("Maximum value of loot possible within given stipulated bits=%d ",unboundedKnapsack(W,size,fin_val,huffman_len)); 
  58.     return 0;
  59. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum value of loot possible within given stipulated bits=195
https://ideone.com/PDcUAx
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!