i got a bag which can take "n" kilograms inside of him
and i have a list of items in which each item has a different weight.
i need to calculate a combination for which it will fill the bag as much as it could
without passing the n kilograms mark.
i got a function which calculates if amongnt the array we have a combination
which sum equals n (S=n)
how to change it so it will calculate a combination for which it will fill the bag as much as it could
without passing the n kilograms mark. S<=n
??
Code:
#include <stdio.h>
void printArr(int arr[], int n)
{
int i ;
puts("");
for (i=0; i<n; i++)
printf (" %d",arr[i]);
puts("");
}
int SubsetSum(int arr[], int n, int S, int subseq[],int count)
{
int withCurrent, withoutCurrent;
if (S==0)
{
printArr(subseq,count);
return 1;
}
if (S< 0 || !n)
return 0;
subseq[count] = arr[0];
withCurrent = SubsetSum(arr+1,n-1,S-arr[0],subseq, count+1);
withoutCurrent= SubsetSum(arr+1,n-1,S,subseq,count);
return (withoutCurrent || withCurrent);
}
void main()
{
int arr[] = {7, 6, 5,1,7,13,17}, subseq[8];
int S = 14,arrSize = 7;
if (!SubsetSum(arr,arrSize,S,subseq,0))
printf("\nThere is no subsequence\n");
}