競技プログラミング風 C++問題集【第16回】


目次

0/1ナップサック問題(難易度:★★★★☆)

問題

質量 wi、価値 vi のアイテムがN個(i = 0, … N-1)あり、それを合計質量 WT まで入れることができるナップサック(knapsack、 リュックサック・バックパックの古い呼び名のひとつ)がある時、 どのアイテムを入れると、価値の合計が最大になるか?という問題を「0/1 ナップサック問題」と呼ぶ。

質量合計上限、const vector<int>& 型の各アイテムの質量配列・価値配列を引数で受け取り、価値合計の最大値を返す関数 int maxValue(int WT, const vector<int>& wt, const vector<int>& val) を実装しなさい。

ただし、wt と val のサイズは同一とし、それぞれのサイズは100以下とする。

例えば、質量・価値が {10, 60}, {20, 100}, {30, 120} の3つのアイテムがあり、質量合計上限が40の場合、 合計価値の最大値は、1番目・3番目をナップサックに入れた場合なので、180となる。

#include <iostream>       //  標準入出力ライブラリ
#include <vector>
#include <unordered_map>
#include <random>
#include <chrono>
using namespace std;    //  std 名前空間使用
std::mt19937 g_mt(0);            // メルセンヌ・ツイスタの32ビット版、引数は初期シード
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
int maxValue(int WT, const vector<int>& wt, const vector<int>& val) {
    return 0;
}
int main() {
    DO_TEST(maxValue(30, { 10, 20, 30 }, { 60, 100, 120 }) == 160);
    DO_TEST(maxValue(40, { 20, 30, 10 }, { 60, 100, 120 }) == 220);
    DO_TEST(maxValue(50, { 10, 30, 20 }, { 100, 60, 110 }) == 210);
    DO_TEST(maxValue(50, { 30, 20, 40, 10 }, { 60, 100, 120, 150 }) == 270);
    DO_TEST(maxValue(60, { 10, 20, 30, 40 }, { 60, 100, 120, 150 }) == 280);
    DO_TEST(maxValue(70, { 10, 20, 30, 40 }, { 60, 100, 120, 150 }) == 310);
    DO_TEST(maxValue(80, { 10, 20, 30, 40 }, { 60, 100, 120, 150 }) == 330);
    DO_TEST(maxValue(80, { 10, 20, 30, 40, 50, 60 }, { 60, 100, 120, 150, 160, 170 }) == 330);
    DO_TEST(maxValue(100, { 10, 20, 30, 40, 50, 60 }, { 60, 100, 120, 150, 160, 170 }) == 430);
    //
    if (1) {
        const int N = 100;  //  アイテム数
        const int SUM = (N+1)*N/2 * 10;
        vector<int> wt(N), val(N);
        int w = 0;
        for (auto& x : wt) x = (w += 10);
        for (auto& x : val) x = (g_mt() % 100 + 1) * 10;
        auto start = std::chrono::system_clock::now();      // 計測スタート時刻を保存
        maxValue(SUM/2, wt, val);
        auto end = std::chrono::system_clock::now();       // 計測終了時刻を保存
        auto dur = end - start;        // 要した時間を計算
        auto msec = std::chrono::duration_cast<std::chrono::milliseconds>(dur).count();
        cout << msec << "milliseconds.\n";
        DO_TEST( msec < 1000 );     //  1秒未満で解けたか?
    }
    //
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

関連記事

競技プログラミング風 C++問題集【第16回】

目次 0/1ナップサック問題(難易度:★★★★☆) 0/1ナップサック問題(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主 […]
コメントなし

競技プログラミング風 C++問題集【第15回】

目次 ポーカー:役判定(難易度:★★★☆☆) ポーカー:役判定(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi […]
コメントなし

競技プログラミング風 C++問題集【第14回】

目次 無向グラフ(難易度:★★★☆☆) 無向グラフ(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第13回】

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第13回~第16回(シーズン4)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで […]
コメントなし

競技プログラミング風 C++問題集【第12回】

目次 文字列比較(難易度:★★★★☆) 文字列比較(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第11回】

目次 クローズド・ナイト・ツアー(難易度:★★★★☆) クローズド・ナイト・ツアー(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研 […]
コメントなし

競技プログラミング風 C++問題集【第10回】

目次 オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・ […]
コメントなし

競技プログラミング風 C++問題集【第9回】

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第9回~第12回(シーズン3)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで正 […]
コメントなし

競技プログラミング風 C++問題集【第8回】

目次 文字列クラス(難易度:★★★★☆) 文字列クラス(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C+ […]
コメントなし

競技プログラミング風 C++問題集【第7回】

目次 数独(難易度:★★★☆☆) 数独(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中 […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP