题解 P1060 【开心的金明】

Pethly_Cat · 2019-09-30 20:36:41 · 题解

听说津津为课程烦恼，金明一家住进了新房...

好了不皮了，现在开始正式的题解！

题目传送门

这个题目是一个01背包的模板题，套一个模板便可以AC。

可是怎么写呢？

01背包，就是最简单的背包问题，有一个总钱数（背包的重量）n和物品的总数m，让你求能装下的最大的价值。不熟悉的可以点这里

由此我们可以推出一个动态转移方程：f[j]=max(f[j],f[j-w[i]]+c[i])。

01背包的模板代码如下：

for(int i=1;i<=n;i++){
    for(int j=m;j>=w[i];j--){
        if(j<w[i]) f[j]=f[j-1];//为了防止数组越界
        else f[j]=max(f[j],f[j-w[i]]+c[i]);//动态转移方程
    }
}

好了，既然有了模板，我们就可以轻松地打出这题的AC代码了：

#include<bits/stdc++.h>//万能头文件
using namespace std;
int w[31],c[31],f[50001];
int main()
{
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>c[i];
        c[i]*=w[i];//如题，用物品的价格乘重要度
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            if(j<w[i]) f[j]=f[j-1];
            else f[j]=max(f[j],f[j-w[i]]+c[i]);//动态转移方程
        }
    }
    cout<<f[m];
    return 0;
}

没有优化过的代码如下（方便蒟蒻参考）

#include<bits/stdc++.h>
using namespace std;
int w[31],c[31],f[31][20001];
int main()
{
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    cin>>w[i]>>c[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j<w[i]) f[i][j]=f[i-1][j];
            else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);//动态转移方程
        }
    }
    cout<<f[n][m];
    return 0;
}//临时手打，可能不会过

最后，给大家推荐几道背包练习题：

采药

疯狂的采药

装箱问题

祝大家CSP2019，rp++！