Life And Death In The Desert - Part 2

Computer Science Level 5

Gina is traveling with Tom into the desert, and she'll be carrying all of their food. She can carry a maximum of $9.5 \text{ kg},$ and has $5500\text{ cm}^3$ of space to carry supplies in her bag. Gina can pick from the following collection of supplies:

$\quad\,$ Food item - Weight / Volume / Calories

granola bars - 240 g / 400 cm $^3$ / 900 calories
potato chips - 135 g / 400 cm $^3$ / 650 calories
beef jerky - 2800 g / 1500 cm $^3$ / 5000 calories
almonds - 410 g / 410 cm $^3$ / 950 calories
apples - 182 g / 190 cm $^3$ / 95 calories.

What is the largest number of calories she can bring with them, given her constraints?

Note: Gina can bring as many as she wants of each of the above items.

The answer is 16945.

8 solutions

Thaddeus Abiy
Mar 4, 2014

Same solution as Part 1 ,except we have two constraints this time. I again used recursion with memoizaion because I was too lazy for a $DP$ solution.If MaxCals is the maximum amount of calories for a given Weight and Volume limit then it can be defined recursively as

$MaxCals=max({MaxCals(Weight-w_{0},Volume-v_{0}),MaxCals(Weight-w_{1},Volume-v_{1})... } )$

for some weight,volume pair $(w_{i},v_{i})$ in the set of supplies.

Table = { 900 : (240,400) , 650:(135,400) , 5000:(2800,1500),
          950: (410,410) , 95:(182,190) }

Save = {} #Memoize values to avoid recomputation
def MaxCals( Weight , Vol ):
    Key = (Weight,Vol)
    if Key in Save:
        return Save[Key]
    if Weight < 0:
        return 0
    if Vol < 0:
        return 0
    if Weight == Vol == 0:
        return 0
    Max = 0
    for item in Table:
        w , v = Table[item]
        if w > Weight or v > Vol:continue
        Val = MaxCals(Weight-w,Vol-v)+item
        if Val > Max:
            Max = Val


    Save[Key]=Max
    return Max

print MaxCals(9.5*1000,5500)

Lokesh Sharma
Mar 6, 2014

Solution in Python:

bestCal = 0
for p in range(int(min(9500/240, 5500/400))+1):
    for q in range(int(min(9500/135, 5500/400))+1):
        for r in range(int(min(9500/2800, 5500/1500))+1):
            for s in range(int(min(9500/410, 5500/410))+1):
                for t in range(int(min(9500/182, 5500/190))+1):
                    if 240*p + 135*q + 2800*r + 410*s + 182*t <= 9500:
                        if 400*p + 400*q + 1500*r + 410*s + 190*t <= 5500:
                            totCal = 900*p + 650*q + 5000*r + 950*s + 95*t
                            if totCal > bestCal:
                                bestCal = totCal
print bestCal

Samarth Bhargav
Mar 5, 2014

The lazy solution: (Probably not the best) You can change th to 11 to verify it is indeed the max.

ma = 0
th = 10

for i in range(th):
    for j in range(th):
        for k in range(th):
            for l in range(th):
                for m in range(th):
                    wt = i*240 + j * 135 + k * 2800 + l * 410 + m * 182
                    if wt > 9500:
                        continue
                    vol = i*400 + j * 400 + k * 1500 + l * 410 + m * 190
                    if vol > 5500:
                        continue
                    cal = i*900 + j * 650 + k * 5000 + l * 950 + m * 95
                    if cal > ma:
                        ma = cal

Sometimes the lazy solution is the easiest to understand and more easily debugged. The problem did not specify any constraints on the solution for speed or memory optimization.

Richard Levine - 6 years, 1 month ago

Shaurya Chats
Mar 5, 2014

In C++,

int main()
{
srand(time(NULL));
int food[5][3] = {{240,400,900},{135,400,650},{2800,1500,5000},{410,410,950},{182,190,95}};
int maxcal = 0;
while(!kbhit()) {
int a = rand() % 14;
int b = rand() % 14;
int c = rand() % 4;
int d = rand() % 14;
int e = rand() % 30;
int weight = a*food[0][0]+b*food[1][0]+c*food[2][0]+d*food[3][0]+e*food[4][0];
int vol = a*food[0][1]+b*food[1][1]+c*food[2][1]+d*food[3][1]+e*food[4][1];

if(weight <=9500 && vol <= 5500) {
          int cal = a*food[0][2]+b*food[1][2]+c*food[2][2]+d*food[3][2]+e*food[4][2];
          if (cal > maxcal) {cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\nMax Calory:"<<cal<<"\n"; maxcal = cal; }}}                
 return 0;
}

include <iostream>

using namespace std;

int bruteforce(int w,int v,int c,int zed){

int profit=c;

if(w<=9500&&v<=5500){

     int a,b,cal;

    for(int z=zed;z<5;z++){

        if(z==0){

            a=240;

            b=400;

            cal=900;

        }

        else if(z==1){



            a=135;

            b=400;

            cal=650;

        }

        else if(z==2){

            a=2800;

            b=1500;

            cal=5000;



        }

        else if(z==3){



            a=410;

            b=410;

            cal=950;

        }

        else{

            a=182;

            b=190;

            cal=95;

        }

        if((w+a<=9500)&&(v+b<=5500)){

            profit=max(profit,bruteforce(w+a,v+b,c+cal,z));

        }

    }

    return profit;

}

return 0;

}

int main()

{

cout<<"solution is ";

cout<<bruteforce(0,0,0,0);

return 0;

}

Aditya Mishra - 7 years, 3 months ago

Vishal Mittal
Dec 30, 2018

C++ solution using Multidimensional Knapsack (MKP) with more than one constraints (here 2 constraints) :

#include<iostream>
using namespace std;

int knapsackDP(int wt1[], int wt2[], int price[],int N,int W1, int W2)
{
    int dp[6][9501][5501] = {0};
    for(int n=0;n<=N;n++)
    {
        for(int w1=0;w1<=W1;w1++)
        {
            for(int w2 = 0; w2 <= W2; w2++)
            {
                if(n==0||w1==0||w2==0)
                {
                    dp[n][w1][w2] = 0;
                }
                else
                {
                    int inc=0,exc = 0;
                    if(wt1[n-1]<=w1 && wt2[n-1]<=w2)
                    {
                        inc = price[n-1] + dp[n][w1-wt1[n-1]][w2-wt2[n-1]];
                    }
                    exc = dp[n-1][w1][w2];
                    dp[n][w1][w2] = max(inc,exc);
                }
            }
        }
    }
    return dp[N][W1][W2];
}

int main()
{
    int wts1[] = {240, 135, 2800, 410, 182};
    int wts2[] = {400, 400, 1500, 410, 190};
    int prices[ ] ={900, 650, 5000, 950, 95};
    int N = 5;
    int W1 = 9500;
    int W2 = 5500;
    cout<<knapsackDP(wts1, wts2,prices,N,W1, W2)<<endl;
    return 0;
}

Rohit Agarwal
Apr 10, 2014

Not very efficient but ok for small n... #include<stdio.h\> int check(int ,int ,int*,int,int,int); int max(int x , int y) { return x>y?x:y; } int main() { int wt[5] = {240,135,2800,410,182}; int space[5] = {400,400,1500,410,190}; int cal[5] = {900,650,5000,950,95}; int W = 9500; int S = 5500; printf("%d",check(wt,space,cal,W,S,5)); } int check(int *wt,int *space,int *cal,int W,int S,int n) { if(n== 0 || W ==0 || S==0) return 0; if(wt[n-1] > W || space[n-1] > S) return check(wt,space,cal,W,S,n-1); else return max(cal[n-1] + check(wt,space,cal,W-wt[n-1],S-space[n-1],n),check(wt,space,cal,W,S,n-1)); }

Brian Chen
Mar 8, 2014

A Haskell solution using a triple of Ints to represent food and the list monad to represent nondeterminstic choice transformed with the StateT monad to record how much food we have so far. What?

import Control.Monad.State
import Data.Ord
import Data.List
foods = [(240, 400, 900), (135, 400, 650), (2800, 1500, 5000), (410, 410, 950), (182, 190, 95)]
(w1,v1,c1) & (w2,v2,c2) = (w1+w2, v1+v2, c1+c2)
canCarry (w, v, _) = w <= 9500 && v <= 5500
calories (_, _, c) = c
load cur add = takeWhile canCarry . scanl (&) cur $ repeat add
main = print . maximum . map calories $ execStateT (forM_ foods
    (\food -> do cur <- get; lift (load cur food) >>= put)) (0,0,0)

Tanmay Gupta
Mar 8, 2014

A variant of 0-1 knapsack problem, solved using the concept of Dynamic Programing in MATLAB

function choicenew= DP(C,W,V,weight,volume,n)

choicenew=zeros(1,size(C,2));
if(n<=0)
    choicenew=zeros(1,size(C,2));
else
    choice=zeros(2,size(C,2));
    if(W(n)<=weight&& V(n)<=volume)
        choice(1,:)=DP(C,W,V,weight-W(n),volume-V(n),n-1);
        choice(1,n)=1;
        choice(2,:)=DP(C,W,V,weight,volume,n-1);
        choice(2,n)=0;
        cost(1)=C*choice(1,:)';
        cost(2)=C*choice(2,:)';
        [x idx]=max(cost);
        choicenew=choice(idx,:);
    else
        choicenew=DP(C,W,V,weight,volume,n-1);
        choicenew(n)=0;
    end
end

Call the function as follows:

clear all
close all 
clc
C = [900 650 5000 950 95];
W = [240 135 2800 410 182];
V = [400 400 1500 410 190];
C1 = repmat(C,1,4);
W1 = repmat(W,1,4);
V1 = repmat(V,1,4);
choicenew= DP(C1,W1,V1,9500, 5500,20);

Life And Death In The Desert - Part 2

The answer is 16945.

8 solutions

include <iostream>

0 pending reports