algorithm - Find a subset with sum within a range -

-

how can find subset of array sum of elements within given range?

for example:

let = [ 1, 1, 3, 6, 7, 50] let b = getsubsetsumrange(3, 5)

so b potentially [1, 1, 3], [1, 3], [3], [1, 3]; doesn't matter order need 1 of them.

you use dynamic programming approach solve problem.

let f[i][j] have value true if possible select numbers among numbers original subset a[1..i] sum equal j.

i vary 1 length of a, , j 0 max inclusively, max second number given range.

f[i][0] = true i definition (you can select empty subset).

then f[i][j] = f[i - 1][j - a[i]] | f[i - 1][j]

logically means if can select subset sum j elements 1..i-1, can subset 1..i, , if can select subset sum j - a[i] elements 1..i-1, adding new element a[i] subset, can desired sum j.

after have calculated values of f, can find f[n][j] true values j lying in desired range.

say have found such number k. algorithm find required set that:

for = n..1:     if f[i - 1][k - a[i]] == true          output a[i] answer          k -= a[i]          if k == 0              break

Comments

Post a Comment

Popular posts from this blog

java - nested exception is org.hibernate.exception.SQLGrammarException: could not extract ResultSet Hibernate+SpringMVC -

-
i trying fetch records database , having above error this classs appropriate getters , setters public class user { private int id; private string username; private string password; private string email; i have create database , inserted data below configuration <bean id="datasource" class="org.apache.commons.dbcp2.basicdatasource" destroy-method="close"> <property name="driverclassname" value="com.mysql.jdbc.driver"/> <property name="url" value="jdbc:mysql://localhost:3306/usersdb"/> <property name="username" value="root"/> <property name="password" value=""/> </bean> this complete stacktrace severe: servlet.service() servlet [appservlet] in context path [/spring] threw exception [request processing failed; nested exception org.hibernate.exception.sqlgrammarexception: not ...
Read more

sql - Postgresql tables exists, but getting "relation does not exist" when querying -

-
Image
i have postgresql db number of tables. if query: select column_name information_schema.columns table_name="my_table"; i list of columns returned properly. however, when query: select * "my_table"; i error: (programmingerror) relation "my_table" not exist 'select *\n "my_table"\n' {} any thoughts on why can columns, can't query table? goal able query table. you have include schema if isnt public one select * <schema>."my_table" or can change default schema show search_path; set search_path my_schema; check table schema here select * information_schema.columns for example if table on default schema public both works ok select * parroquias_region select * public.parroquias_region but sectors need specify schema select * map_update.sectores_point
Read more

asp.net mvc - breakpoint on javascript in CSHTML? -

-
i have .cshtml file has javascript tag. within script tag have few lines of javascript. first line of javascript refers property in @viewbag. other javascript lines plain script without mvc related references. observation: can place breakpoints (visual studio 2015) on each of these javascript lines. however, breakpoints has white dot in center of breakpoint symbol (red circle) except line @viewbag reference (this particular line not have white dot in center). it seems breakpoint without white dot hit during run-time. question: can explain going on here? white dot mean? why plain red breakpoint line line hitting breakpoint? the visual studio debugger expecting debug actual server-side code within .cshtml file opposed client-side javascript within it. iirc, visual studio allow debug javascript code expected in internet explorer (and possibly edge), other browsers want use either third-party tool or developer tools (f12) within browser. an easy approach take advant...
Read more