reset;

option randseed'';
option solver cplex;


param C := round(Uniform(100,100));	   			# capacity
param N := round(Uniform(30,30));	   			# number of items
param u {i in 1..N} := round(Uniform(3,8)/0.25)*0.25;   	# utility of item i
param s {i in 1..N} := round(Uniform(1,12));   	# space of item i


###########  Linear Programming Approach  #################

var x {i in 1..N} binary;	   					# binary variables

maximize   LP: sum{i in 1..N} u[i]*x[i]; 		# objective

subject to NB: sum{i in 1..N} s[i]*x[i] <= C;  	# budget con.

solve;	   										# solution

display x,s,u;	   								# output

param LPtime default 0;
let LPtime:= _ampl_time;                        # runtime


###########  Dynamic Programming Approach  #################

# value function V[k,c] := best utility of "having item set {k,...,N} and capacity c left"

param V{k in 1..N+1,c in 0..C} := if k=N+1 or c=0 then 0 else   
               max{a in 0..(if s[k]<=c then 1 else 0)} (a*u[k] + V[k+1,c-a*s[k]]);

param aopt{k in 1..N} default 0;                # was item k used in optimal selection?
param Copt{k in 0..N} default 0;                # budget used considering items {1,...,k}

for{k in 1..N} {                                # recursion: add item {k} to item set {k+1,...,N}

let aopt[k]:=      if  C-Copt[k-1] -s[k]>=0     # does item k fit in remaining budget?
               and V[k,C-Copt[k-1]]-u[k] = V[k+1,C-Copt[k-1]-s[k]]  # yields item k the best additional utility?
			       then 1 else 0;
				   
let Copt[k]:= Copt[k-1] + s[k]*aopt[k];         # budget used (when k is added to item set {1,...,k-1})                   

                };

param U_DPopt:= sum{i in 1..N} aopt[i]*u[i];    # total utility (full set of potential items)
param S_DPopt:= sum{i in 1..N} aopt[i]*s[i];    # total budget used (=Copt[N])


display V;

display aopt,x;                                 # decision          comparison DP vs. LP
display U_DPopt,LP;                             # total utility     comparison DP vs. LP
display S_DPopt, sum{i in 1..N} s[i]*x[i], C;   # total budget used comparison DP vs. LP

display LPtime, _ampl_time - LPtime;            # runtime           comparison DP vs. LP