Knapsack Problem

Given weights and values of n gift items. We have a box of capacity W. Find a solution such that the total value of gifts in the box is maximum.
In this Problem, we have two integer arrays value[0,1,2,…,n-1] and weight[0,1,2,3…,n-1],it represents the values and weights associated with n items resp. Given an integer W which represents the total capacity of the box. Write a Program to find the maximum value V which is the sum of the subset of values (value[]) such that the sum of the weight of this subset is smaller than or equal to W.
We either have to pick the complete gift item or don’t pick it.

Also known as 0-1 Knapsack Problem because we cannot split the item mentioned. Either we don’t pick the item (i.e 0) or pick the complete item (i.e 1).

Find Solution here

Buffer Overflow

Rewrite the program shown below so that it is no longer vulnerable to a buffer overflow.

int main (int argc, char *argv[]) {
    bool valid = false;
    char str1[8];
    char str2[8];

/* This is some function that assigns some string to str1 */

/* Read a string from standard input device (eg. keyboard) */

    if ( strncmp(str1, str2, 8) == 0 )

        valid = true;
    printf (“buffer1: str1(%s), str2(%s), valid(%d)n”, 
                                          str1, str2, valid);
Find Solution here

Subtle Bug

The variable d is less than the Total elements, but still the if condition did not evaluate to true. Find the Bug.

#include <stdio.h>
int array_one[]={1,2,3,4,5,6};
#define TOTAL_ELEMENTS (sizeof(array_one)/sizeof(array_one[0]))

int main()
  int d=-1;
    printf(“d is less than Total no. of elemnts in the array”); //execution never comes her
    printf(“d is greater than total elements in the array”); //this will get printed
  return 0;

Find Answer here