TOYS

Last Updated on March 23, 2022 by Ria Pathak

Concepts Used

DYNAMIC PROGRAMMING

Difficulty Level

Easy.

Problem Statement :

Once upon a time, Arya visited a toy store. As Arya is a small kid he is attracted to every toy. But Arya has a bag of capacity C and each toy occupies a definite volume of his bag. He would like to fill his bag so that when he goes home he can play with them all.
Arya plays with each toy turn by turn and after playing with a specific toy his happiness increases by a specified amount which is different for a different toy.
As a smart kid Arya wants to be the happiest person, help him to choose his toys. Each toy can be selected just one time.
Find the maximum value of happiness Arya can reach.

See original problem statement here

EXPLANATION:

NOTE: This is basically a modification of knapsack problem.

BRUTE FORCE:

Brute force is a straightforward approach to solving a problem, usually directly based on the problem’s statement and definitions of the concepts involved. If there are n items to choose from, then there will be 2n
possible combinations of items for the knapsack. An item is either chosen or not chosen. A bit string of 0’s and 1’s is generated which is of length n. If the ith symbol of a bit string is 0, then the ith item is not chosen and if it is 1,
the ith item is chosen.

ALGO:

   let w[1], ... , w[n] be the weights of the items
   let v[1], ... , v[n] be the values of the items
   let maxWeight be the capacity of the bag
   bestValue := 0
   function solve(n, currentWeight, currentValue) {
    if n = 0 and currentWeight <= maxWeight and currentValue     bestValue:
        bestValue := currentValue
    if n = 0: return
    don't pack this item
    solve(n-1, currentWeight, currentValue)
     pack this item
    solve(n-1, currentWeight + w[n], currentValue + v[n])
    }
    solve(n, 0, 0)
    print bestValue

You are encouraged to implement the above brute force before looking at the solution.

What did you get?TLE?
You got TLE because if you observe closely , you could easily see that this approach takes O(N*2ⁿ)

OPTIMIZATION:

DYNAMIC PROGRAMMING:

Here’s the general way the problem is explained – Consider a thief gets into a home to rob and he carries a knapsack. There are fixed number of items in the home – each with its own weight and value – Jewellery, with less weight and highest value vs tables, with less value but a lot heavy. To add fuel to the fire, the thief has an old knapsack which has limited capacity. Obviously, he can’t split the table into half or jewellery into 3/4ths. He either takes it or leaves it.

Had it not been so,we could have easily used greedy approach.

The way this is optimally solved is using dynamic programming – solving for smaller sets of knapsack problems and then expanding them for the bigger problem.

We will use two variables to represent the states of DP.

i – The current index we are working on.

R – It contains the remaining capacity of each and every knapsack.

Now, at each step, we will have k+1 choices.

Reject index i.

Put item i in knapsack 1.

Put item i in knapsack 2.

Put item i in knapsack 3.
…
k+1) Put item i in knapsack k.

In simpler words

The knapsack problem is a problem in combinatorial optimization: given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items . The most famous knapsack problem is the binary (0–1) knapsack problem, where the decision maker is allowed to pick (1) or not to pick (0) the item, in other words, the items are not dividable.

The problem can be formulated as follows:

Let there be N items, x1 to xn where xi has the vi value and wi weight . The maximum weight the knapsack can carry is W. It is common to assume that all values and weights are non-negative.

To illustrate, assume w1,w2,w3..wn are strictly positive integers. Define m[i,w] to be the maximum value that can be attained when the weight is less than or equal to w using items up to i. The definition of is then as follows:

1. m[i,w] = m[i-1,w] if wi>w(the new item is more than the current weight limit)
2. m[i,w] = max( m[i-1,w] ,m[i-1,w-wi]+vi ) if wi `

SOLUTIONS:

 #include <stdio.h>
     int main()
    {
    //write your code here
    int t;scanf("%d",&t);
    while(t--)
    {
    int n,c;
    scanf("%d%d",&n,&c);
    int dp[n+1][c+1];
    int wt[n+1],val[n+1];
    for(int i=1;i<=n;i++)
    scanf("%d",&wt[i]);
    for(int i=1;i<=n;i++)
    scanf("%d",&val[i]);
    for(int i=0;i<=c;i++)
    dp[0][i]=0;
    for(int i=1;i<=n;i++)
    {
      for(int j=0;j<=c;j++)
      {

          dp[i][j]=dp[i-1][j];
          if(wt[i]<=j)
          {
            dp[i][j]=dp[i][j]>dp[i-1][j-wt[i]]+val[i]?dp[i][j]:dp[i-1][j-wt[i]]+val[i];
          }

      }
    }
    printf("%d\n",dp[n][c]);
    }
    return 0;
    }

#include <bits/stdc++.h>
    using namespace std;

    int bag(int C, int V[], int H[], int n)  
    {  
    int i, w; 
    int K[n+1][C+1]; 
    for (i = 0; i <= n; i++) 
    { 
       for (w = 0; w <= C; w++) 
       { 
           if (i==0 || w==0) 
               K[i][w] = 0; 
           else if (V[i-1] <= w) 
                 K[i][w] = max(H[i-1] + K[i-1][w-V[i-1]],  K[i-1][w]); 
           else
                 K[i][w] = K[i-1][w]; 
       } 
    } 

     return K[n][C]; 
    }  
     int main()
     {


     int t;
     cin>>t;
     while(t--)
     {
      int n,c;
     cin>>n>>c;
     int v[n],h[n];
     for(int i=0;i<n;i++)cin>>v[i];
     for(int i=0;i<n;i++)cin>>h[i];

      cout<<bag(c,v,h,n)<<endl;;

       }    
     }

import java.util.*;
    import java.io.*;
    class Knapsack 
    { static int max(int a, int b) 
    { 
        return (a > b) ? a : b; 
    } 
    static int knapSack(int W, int wt[], int val[], int n) 
    { 
        int i, w; 
        int K[][] = new int[n + 1][W + 1];  
        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]; 
            } 
        } 

        return K[n][W]; 
      } 


    // Driver program to test above function 
     public static void main(String args[]) 
    { Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
            int W = sc.nextInt();
            int val[] = new int[n]; 
        int wt[] = new int[n];
        for(int i=0;i<n;i++)
            {
                wt[i] = sc.nextInt();
            }
            for(int i=0;i<n;i++)
            {
                val[i] = sc.nextInt();
            }
    System.out.println(knapSack(W, wt, val, n)); }
    } 
    }

This article tried to discuss the concept of Dynamic Programming. Hope this blog helps you understand and solve the problem. To practice more problems on Dynamic Programming you can check out MYCODE | Competitive Programming.