SP22804 KNPSACK - Knapsack 题解

ACtheQ · 2023-10-22 10:37:26 · 题解

经典的完全背包题目。

完全背包，X 为背包的容量，P_i 为价格，W_i 为重量。

由于每种魔法粉数量是无限的，所以是完全背包。

完全背包模板：

for(int i=1;i<=m;i++)
{
    for(int j=w[i];j<=t+w[i];j++) dp[j]=min(dp[signed(j-w[i])]+v[i],dp[j]);
}

接下来，跟完全背包有些不同。

由于魔法粉价格不为整数，所以用浮点类型。

题目同时说明了要买到至少 X 毫克魔法粉。

所以答案为 X \le i \le 10^7，对所有 dp_i 取最小值。

注意输出时保留两位小数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
double t;
int m;
double w[10005];
double v[10005],dp[10000005];
signed main()
{
    cin>>t>>m;
    for(int i=1;i<=m;i++) cin>>w[i]>>v[i];
    for(int i=1;i<=10000000;i++) dp[i]=1e18;
    dp[0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=w[i];j<=t+w[i];j++) dp[j]=min(dp[signed(j-w[i])]+v[i],dp[j]);
    }
    double ans=1e18;
    for(int i=t;i<=10000000;i++) ans=min(ans,dp[i]);
    printf("%.2lf",ans);
    return 0;
}