dynamic programming - How does one solve this optimization? -

-

in videogame, there n levels, each 1 requires have amount of energy in order win level. start game @ level 0 0 energy, , every time win level, spend energy level requires (your energy can't go below 0). each level has 0, 1, or more shops sells energy amount e @ cost c. if find without enough energy pass level, lose because can't go previous levels buy other shops. whenever buy shop, new amount of energy e (the 1 shop sells), is, doesn't sum previous energy.

the question: minimum money necessary in order win n levels? (assuming money infinite , can buy shops want,... want optimize buys necessary)

i'm interested know how 1 finds solution this. problem solving technique solves kind of problems, if so, can explain?. there similar known problems should study first?

i tried using recursive backtracking, hope of finding overlapping states , use dynamic programming, didn't find them. states where: shops, fork 2 branches... buys shop, or doesn't.

this easy problem because energy doesn't sum. means energy e(n) after buying in level n not depend on did in levels 0...n-1. means can work backwards; last shops have bought energy reach end? , each of candidates, shops before them must have bought energy reach last shop?


Comments

Post a Comment

Popular posts from this blog

sequelize.js - Sequelize group by with association includes id -

-
so when requesting group sequelize follows: return models.workingcalendar .findall({ attributes: [ 'workingcalendar.periodid', 'workingcalendar.date', 'period.name' ], include: [ { model: models.period, attributes: [] } ], where: { getsudoid: currentgetsudo.id, unitplantid: unitplantid }, group: ['workingcalendar.periodid', 'workingcalendar.date', 'period.name'], }); sequelize run query: select [workingcalendar].[id], [workingcalendar].[periodid], [workingcalendar].[date], [period].[name] [workingcalendars] [workingcalendar] left outer join [periods] [period] on [wor
Read more

android - Robolectric "INTERNET permission is required" -

-
i'm getting error when create activity robolectric: java.lang.illegalargumentexception: internet permission required. this i'm doing: @config(constants = buildconfig.class, sdk = testconfig.min_sdk_unit_tests, manifest = "src/main/androidmanifest.xml") @runwith(robolectricgradletestrunner.class) public class atest { @test public void testtrackdonotaskmeagainselected() throws exception { final anactivity activity = robolectric.buildactivity(anactivity.class).create().get(); } update 1: our current setup, have manifests: app/src/androidtest/androidmanifest.xml app/src/debug/androidmanifest.xml app/src/main/androidmanifest.xml app/src/test/androidmanifest.xml i found debug executed instead of test , that's why permission in app/src/test/androidmanifest.xml ignored. add manifest: <uses-permission android:name="android.permission.internet" />
Read more

java - Android raising EPERM (Operation not permitted) when attempting to send UDP packet after network connection -

-
when responding supplicant_state_changed_action broadcast , attempting send udp packet, exception: java.net.socketexception: sendto failed: eperm (operation not permitted) @ libcore.io.iobridge.maybethrowaftersendto(iobridge.java:542) @ libcore.io.iobridge.sendto(iobridge.java:511) @ java.net.plaindatagramsocketimpl.send(plaindatagramsocketimpl.java:184) @ java.net.datagramsocket.send(datagramsocket.java:305) @ com.mycompany.app.serviceclass.discover(serviceclass.java:355)at com.mycompany.app.serviceclass.access$600(serviceclass.java:39) @ com.mycompany.app.serviceclass$statemachine.run(serviceclass.java:242) @ java.lang.thread.run(thread.java:818) caused by: android.system.errnoexception: sendto failed: eperm (operation not permitted) @ libcore.io.posix.sendtobytes(native method) @ libcore.io.posix.sendto(posix.java:211) @ libcore.io.blockguardos.sendto(blockguardos.java:278) @ libcore.io.iobridge.sendto(iobridge.java:509) @ java.net.plaindat
Read more