acwing::acwing2 命名空间参考

1. 01背包问题

更多...

类
struct	status

函数
int	main (istream &cin, ostream &cout)
	TEST (acwing2, case1)

详细描述

1. 01背包问题

函数说明

main()

int acwing::acwing2::main	(	istream &	cin,
		ostream &	cout
	)

在文件 acwing408.cpp 第 1806 行定义.

                                              {
            int N, V;
            cin >> N >> V;
            vector<int> v     = vector<int>(N);
            vector<int> w     = vector<int>(N);
            vector<status> dp = vector<status>(V + 1, status{
                                                              .w    = 0,
                                                              .free = vector<bool>(N, true)});
            for(int i = 0; i < N; i++) {
                cin >> v[i] >> w[i];
            }
            for(int i = 0; i <= V; i++) {
                for(int j = 0; j < N; j++) {
                    if(dp[i].free[j]) {
                        int next_w = dp[i].w + w[j];
                        int next_v = i + v[j];
                        if(next_v <= V && next_w > dp[next_v].w) {
                            dp[next_v].w       = next_w;
                            dp[next_v].free    = vector<bool>(dp[i].free);
                            dp[next_v].free[j] = false;
                        }
                    }
                }
            }
            cout << dp[V].w;
            return 0;
        }

引用了 acwing::acwing2019::N , 以及 acwing::acwing2::status::w.

被这些函数引用 TEST().

TEST()

acwing::acwing2::TEST	(	acwing2	,
		case1
	)

在文件 acwing408_test.cpp 第 1990 行定义.

                             {
            istringstream in("4 5\n"
                             "1 2\n"
                             "2 4\n"
                             "3 4\n"
                             "4 5");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("8", ans);
        }

引用了 main().