質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

91.36%

  • アルゴリズム

    280questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • 再帰

    22questions

    情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

ナップサック問題 アルゴリズム

解決済

回答 1

投稿 2015/06/05 14:31

  • 評価
  • クリップ 4
  • VIEW 5,303

doratai

score 25

現在javaを用いて再帰の学習をしています。
再帰がよくわかりません。
具体例として
ナップサック問題を解く再帰的なアルゴリズムを教えてください。



  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+5

こんなんいかがでしょう。
package a;

import java.util.ArrayList;
import java.util.List;

public class TT10780 {
    public static void main(String[] args) {
        try {
            Item[] items = new Item[] {
                    new Item("A", 20, 10),
                    new Item("B", 28, 13),
                    new Item("C", 16, 8),
                    new Item("D", 8, 5),
                    new Item("E", 12, 7),
                    new Item("F", 24, 11),
            };

            for(Item i : new HiPriceCombi(items, 30).get()) {
                System.out.println(i.name);
            }
        }
        catch(Throwable e) {
            e.printStackTrace();
        }
    }

    public static class Item {
        public Item(String n, int p, int w) {
            name = n;
            price = p;
            weight = w;
        }

        public String name;
        public int price;
        public int weight;
    }

    public static class HiPriceCombi {
        private Item[] items;
        private int weightCapa;

        public HiPriceCombi(Item[] i, int w) {
            items = i;
            weightCapa = w;
        }

        private int price;
        private int weight;
        private List<Item> combi;

        private int hiPrice;
        private Item[] hiPrCombi;

        public Item[] get() {
            price = 0;
            weight = 0;
            combi = new ArrayList<Item>();
            hiPrCombi = null;
            pick(0);
            return hiPrCombi;
        }

        /**
         * 再帰メソッド
         */
        private void pick(int bgnPos) {
            for(int index = bgnPos; index < items.length; index++) {
                Item item = items[index];

                if(weight + item.weight <= weightCapa) {
                    price += item.price;
                    weight += item.weight;
                    combi.add(item);

                    if(hiPrCombi == null || hiPrice < price) {
                        hiPrice = price;
                        hiPrCombi = combi.toArray(new Item[0]);
                    }
                    pick(index + 1); // ★★★再帰★★★

                    price -= item.price;
                    weight -= item.weight;
                    combi.remove(combi.size() - 1);
                }
            }
        }
    }
}

投稿 2015/06/05 15:44

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

ただいまの回答率

91.36%

関連した質問

  • 解決済

    node.js(jsonwebtoken)の使用可能暗号アルゴリズムについて

    node.jsを用いてopenIdを認証に用いたシステムを express4で作っています。 jsonwebtoken,express-jwtライブラリを用いて作っているのですが、

  • 受付中

    vbscriptで配列内計算

    題名の通りです。 vbscriptで配列内計算する方法はありますか? 1+1にとどまらず、1+1+1+1+1+1+1と伸ばしていくことを前提としております。 説明が足りないと

  • 解決済

  • 受付中

    アルゴリズムの入門書

    アルゴリズム入門の勉強におすすめの書籍、サイトなど教えてもらえないでしょうか? CheckiOというpython学習サイトを進めているのですが、難しくてなかなか進まないのでアルゴ

  • 受付中

    敵AIの経路探索について

    今、Unityで3Dのローグライクを作ろうとしていて敵を作成中なのですが障害物を検索し動的に避けてPlayerを追尾するといったことが中々上手くいっていません。 ちなみにフィ

  • 解決済

    疑似コードの記号について

    疑似コードで記されている、両端に矢印が付いた記号や、両端が四角の記号。 それと、処理の合間に入っている棒。 これらの作用を教えてください。

  • 受付中

    情報技術検定1級の問題でわからないところがあるので教えてください

    アルゴリズムの問題でわからないところがあるので教えてください。 問題 次の流れ図は、底辺の半径がr、高さがhの円錐の体積を求める処理を表している。 流れ図の中の空欄①~④に入れるべ

  • 受付中

    Pythonのxgboostでマルチコア使用方法

    Pythonでxgbを使用しているのですが、高速化するためにマルチコアで動かしたいです。 以下がプログラムです。 xgb_model = xgb.XGBClassifier(n

同じタグがついた質問を見る

  • アルゴリズム

    280questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • 再帰

    22questions

    情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。