重量为小数的背包问题怎么做?

学术版

@[dyc2022](/user/504093) @[Drind](/user/305854) @[TernaryTree](/user/362750) @[what_can_I_do](/user/658973) @[gesong](/user/658198)
by YuRuochen @ 2024-04-26 16:27:52


@[YuRuochen](/user/658786) ~~把重量全部乘上同一个数,然后让它们变成整数就行了~~
by xxboyxx @ 2024-04-26 16:33:00


如果价值为整数且较小的话,或许可以令 $f_i$ 表示价值总和为 $i$ 时的最小总重,参考 [Knapsack 2](https://www.luogu.com.cn/problem/AT_dp_e);价值也很大的话就不会了ww
by hzlqwq @ 2024-04-26 16:33:20


@[xxboyxx](/user/473256) ~~你说得对,但是楼主并未给出有多少位小数······~~
by I_am_jocker @ 2024-04-26 16:33:50


@[YuRuochen](/user/658786) 用map
by litjohn @ 2024-04-26 16:35:01


@[I_am_jocker](/user/1059074) @[YuRuochen](/user/658786) 针 对于这件事,用 double 不可以吗,多一点自己建个库存
by xxs12345 @ 2024-04-26 16:47:11


@[xxs12345](/user/1122479) 我的意思是,重量诸如,12.4561525,15.1316512 的背包问题。hzlqwq 说得很对。
by YuRuochen @ 2024-04-26 16:49:40


借口问重量是有理数(分数)怎么做,感觉这更有趣些
by Iniaugoty @ 2024-04-26 19:42:14


|