ztz(juruo)的第一次**

ztz小蒟蒻第一次发文章,若有错误或可以改进的地方请指出orz

codevs P1014 装箱问题(传送门

解题思路:
一个非常简单的水题,背包的简单应用。平时的背包都是有一个体积V一个价值W,但此题只有V,求如何塞得最满(莫开车)。我的思路是将一个物体的体积大小赋给他自身做价值,接着套用背包模板就好了。不过要注意,最后别忘了输出的是剩余空间。
贴代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int v,n;
int c[50];
int w[50];
int f[200010];
int main()
{
    cin>>v>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        w[i]=c[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=v;j>=c[i];j--)
        {
            f[j]=max(f[j],f[j-c[i]]+w[i]);
        }
    }
    cout<<v-f[v];
    return 0;
}

0 0 votes
文章评分

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

1 评论
最旧
最新 得票最多
Inline Feedbacks
View all comments