I don't have any Japan-centric advice, but I have found that a Backpack is essential, even if you are going to a hotel, and not a hostel.
If you are going to a new city, and don't have arrangements beforehand, check out Expedia last-minute like. It can turn out that their Hotel deals are the best part of the site, and can get as -or close to as- cheap as a hostel (of course, depending on the Hostel as well, of course). This is especially true of areas that do not get many backpackers (I did this alot in Denmark this year, and they don't really have the facilities for backpackers, ie. cheap lodging, like when I went to New Zealand). It helps to add variety to the places you are going, too.
|