题解 | #货船#

货船

链接：https://ac.nowcoder.com/acm/problem/236172 来源：牛客网

有 n个货物，需要装入货船，第 i 个货物的重量是 wi 。货船的最大载重量是 A ，请问在不超过货船最大载重量的前提下，一次最多能运送多少重量的货物。

做法：一眼是01背包，但是无论是物品数量还是重量上限都超过了复杂度和空间复杂度，所以选择去优化背包，01背包其实就是选和不选的选择，非常适合用01字符串去表示，正好可以用stl中的bitset去解决，对于两个状态的字符串，如果这个物品不选，两个状态字符串是相同的，选择这个物品的话，就是多加了a【i】这么多的重量。对于字符串来说就是每个1向右移动了a【i】个单位吧，那么用位运算就能解决最后从最大重量往前遍历，遇到第一个1返回即可。（这里解释一个bit.set(0,1)表示将初始字符串的第0个位置改成1，这样在选不了的情况下也会输出-，还有很多bitset的好用函数自行搜索~）

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
/*inline __int128 read(){
    __int128 x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}*/
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
//用__int128时记得删掉关流
std::bitset<100010> bit;
void slove()
{
    int n,k;
    std::cin>>n>>k;
    std::vector<int> a(n+1);
    for(int i=1;i<=n;i++) std::cin>>a[i];
        bit.set(0,1);
    for(int i=1;i<=n;i++)
    {
        bit|=(bit<<a[i]);
    }
    for(int i=k;i>=0;i--)
    {
        if(bit[i])
        {
            std::cout<<i<<endl;
            break;
        }
    }

}
int main()
{
    int T=1; 
    //std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}