SP22804

linyuhuai · 2021-05-28 22:30:17 · 题解

题意概括：

给定 M 个物品，第 i 个物品重量为 W_i 价格为 P_i ，且每个物品可以取无限次，求出在重量至少为 X 的情况下，最少能花多少钱？

题意分析：

既然每个物品能取无限次，那么这个问题即完全背包，因为价格可能为小数不方便作为数组存储，所以用重量做第一维。在重量至少为 X 的情况下，至少一词代表 重量 ≥X 。可以求出动态转移方程：f_i=\min(f_i,f_{i-w}+p) 。

样例一为例：

3 2
1 1.10
2 0.83

如果背包最高上限只到 X ，那么程序会输出 1.93 ，而不是答案的 1.66 。因为 2\times2 ＞X ，所以搜索不到正确答案。 上限应为 X+W_i-1 。

温馨提示：输出需输出 2 位小数

AC 代码：

#include<bits/stdc++.h>
using namespace std;
float f[100005];
int main() {
    float n,w;
    cin>>w>>n;
    for(register int i=1; i<=100004; i++) {
        f[i]=0x7fff;
    }
    float ans=0x7fff;
    for(register int b=1; b<=n; b++) {
        register float v,wi;
        scanf("%f%f",&v,&wi);
        for(register int i=v; i<=w+v; i++) {
            f[i]=min(f[i],f[int(i-v)]+wi);
            if(i>=w) {
                ans=min(ans,f[i]);
            }
        }
    }
    printf("%.2lf",ans);
}