Comment

Westbrook: 2024-05-11 12:09:51

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e4 + 10;
int m;
int l[N], p[N];
int f[N];
int main()
{
	cin >> m;
	while (m--)
	{
		memset(l, 0, sizeof l);
		memset(p, 0, sizeof p);
		memset(f, 0, sizeof f);
		int n,k;
		cin >> n>>k;
		for (int i = 1; i <= k; i++)
		{
			cin >> l[i] >> p[i];
		}
		for (int i = 1; i <= k; i++)
		{
			for (int j = l[i]; j <= n; j++)
			{
				f[j] = max(f[j], f[j - l[i]] + p[i]);
			}
		}
		cout << f[n] << endl;
	}
	return 0;
}
理解题意，在样例中，94 2,；21 55 88 64.可以理解为背包容量为94，第一个宝石体积21，价值55，第二个宝石体积88，价格为64，且两种宝石能无限用，当然不能超过最大体积，暴力枚举o（n3），过不了，优化一维，二维可过，但空间会爆Mle，故要不断优化到一维

Qaqqaq: 2023-05-05 18:31:09

map 能过

```cpp
#include "helpers.hpp"

#include <algorithm>
#include <iostream>
#include <limits>
#include <map>
#include <vector>

using Prices = std::map<int, int>;

struct Data {
  int total_length{};
  Prices prices{};
};

ALWAYS_INLINE auto get_max_value(int total_length, Prices const& prices) -> int {
  std::vector<int> max_value(narrow_cast<std::size_t>(total_length) + 1, 0);

  for (Index current_total_length{1}; current_total_length <= narrow_cast<Index>(total_length);
       ++current_total_length) {
    auto const end{prices.upper_bound(narrow_cast<int>(current_total_length))};
    for (auto iter{prices.cbegin()}; iter != end; ++iter) {
      max_value[narrow_cast<std::size_t>(current_total_length)]
          = std::max(max_value[narrow_cast<std::size_t>(current_total_length)],
                     max_value[narrow_cast<std::size_t>(current_total_length - iter->first)] + iter->second);
    }
  }

  return max_value[narrow_cast<std::size_t>(total_length)];
}

ALWAYS_INLINE auto read_data(std::istream& istream) -> Data {
  auto const total_length{extract_from<int>(istream)};

  auto const size{extract_from<std::size_t>(istream)};

  Prices prices{};
  for (std::size_t i{}; i < size; ++i) {
    auto const length{extract_from<int>(istream)};
    auto const price{extract_from<int>(istream)};
    prices.emplace(length, price);
  }

  return {total_length, std::move(prices)};
}

#ifndef ENABLE_TEST

auto main() -> int {
  auto const line_size{extract_from<int>(std::cin)};
  for (int i{}; i < line_size; ++i) {
    auto const data{read_data(std::cin)};
    std::cout << get_max_value(data.total_length, data.prices) << '\n';
  }
}

#else

#  include <gtest/gtest.h>

TEST(GetMaxValue, Pass) {
  EXPECT_EQ(0, get_max_value(27, {{35, 41}, {61, 49}, {73, 74}}));
  EXPECT_EQ(220, get_max_value(94, {{21, 55}, {88, 64}}));
  EXPECT_EQ(220, get_max_value(100, {{21, 55}, {35, 41}, {61, 49}, {73, 74}, {88, 64}}));
}

#endif
```

lin zehao: 2023-05-04 18:13:47

1018、1019、1021都能做到时间复杂度为o(背包大小*方案种类数)，即o（n*k），空间复杂度为o（背包大小），即o（n）

lin zehao: 2023-05-04 18:11:14

这题和1019是同一种题，区别在于1019每种宝石只有一个，而1021每种长度的钢材可以有无数个。
        cin >> n >> k;
        int value[10001] = {};
        for (int j = 0; j < k; j++) {
            cin >> s >> v;
            for (int q = 1; q <= n; q++) {//若有限个，则从n开始遍历到1，这样每种宝石只会加一次；若无数个，则从1开始遍历到n，每种钢材可以多次相加。
                if (s <= q) {
                    value[q] = max(value[q - s] + v, value[q]);
                }
            }
        }
        cout << value[n] << endl;

Captain_Jack: 2021-11-01 20:16:28

这难道不是无限背包问题吗? 楼上为何还要创建价格表映射? 求解惑

Jayu204660: 2020-11-25 20:09:17

建议空间换时间，开大的数组。下标就是长度，对应值就是价格。例如开price[10005]存储价格。price[100]=95表示100长度的价格是95

sacrificemoon: 2020-11-03 23:13:21

只要用vector就会超时。。全换成数组就没问题了

flsgavin: 2020-10-23 19:52:13

这个题价格表构建用map<key,value>会超时，直接开数组则不会。这样会不会有点过于追求时间效率而忽略了空间效率？或者有什么更好的解决方法兼顾时间和空间吗？