Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- int max(int a, int b) { return (a > b)? a : b; }
- int knapSack(int W, int wt[], int val[], int n)
- {
- int i, w;
- int maxi;
- int j;
- int K[n+1][W+1];
- // Build table K[][] in bottom up manner
- for (i = 0; i <= n; i++)
- {
- for (w = 0; w <= W; w++)
- {
- if (i==0 || w==0)
- K[i][w] = 0;
- else if (wt[i-1] <= w)
- K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
- else
- K[i][w] = K[i-1][w];
- }
- }
- printf("\n MAKSYMALNA WARTOSC:%d\n", K[n][W]);
- i=n;
- j=W;
- printf("PRZEDMIOTY: \n");
- while(i>0&&j>0){
- if (K[i][j]!=K[i-1][j]) {printf("%d ", i);
- j=j-wt[i-1];
- }
- i--;
- }
- }
- int main()
- {
- int k;
- int i;
- int W;
- printf("Podaj ilosc przedmiotow\n");
- scanf("%d",&k);
- printf ("Ladownosc:\n");
- scanf("%d",&W);
- int n;
- int val[k];
- int wt[k];
- for(i=0;i<k;i++)
- {
- printf("Podaj wage %d przedmiotu",i+1);
- scanf("%d",&wt[i]);
- printf("Podaj cene %d przedmiotu",i+1);
- scanf("%d",&val[i]);
- }
- knapSack(W, wt, val, k);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement