为什么会出现比W-w[j]更大的情况?
查看原帖
为什么会出现比W-w[j]更大的情况?
128761
_builtin__楼主2020/7/12 11:08

请问各位神犇,为什么会出现Wws[j]W-ws[j]elv[i  (1<<(j1))]elv[i\ |\ (1 << (j-1))]值小的情况。

我的代码如下:

#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string.h>

namespace io
{
    using ::std::cin;
    using ::std::cout;
    using ::std::endl;
    using ::std::max;
    using ::std::sort;

    typedef unsigned int uint;
}

using namespace io;

uint N, W;
uint ws[20];
uint sts[1<<18];    //每个电梯状态的最少情况,最终答案为    (1<<18) - 1
uint elv[1<<18];    //状态中,最后一个电梯的剩余空间

void solve()
{
    cin >> N >> W;
    for(uint i = 1; i <= N; ++i)
        cin >> ws[i];
    
    memset(sts, 0x3f, sizeof(sts));
    sts[0] = 1; //无论如何都要使用一个
    elv[0] = W; //对应上面

    //枚举所有状态
    for(int i = 0; i < (1<<N); ++i)
    {
        for(uint j = 1; j <= N; ++j)
        {   
            //牛已经在里面
            if(i & (1 <<(j-1)))  continue;

            //如果放得下,并且比之前的结果更好
            if(elv[i] >= ws[j] && sts[i | (1 << (j-1))] > sts[i])
            {   
                //转移
                sts[i | (1 << (j-1))] = sts[i];
                //因为sts的变化,elv必须变
                elv[i | (1 << (j-1))] = elv[i] - ws[j];
            }
            //如果放得下,并且当前结果和之前结果一样好
            else if(elv[i] >= ws[j] && sts[i | (1 << (j-1))] == sts[i])
            {
                //一样好 sts无需转移
                //elv 转移为更大的保证最优情况
                elv[i | (1 << (j-1))] = max(elv[i] - ws[j], elv[i | (1 << (j-1))]);
            }
            //如果塞不下,并且比之前结果好
            else if(elv[i] < ws[j] && sts[i | (1 << (j-1))] > sts[i] + 1)
            {
                //开一个新的
                sts[i | (1 << (j-1))] = sts[i] + 1;
                //因为sts的变化,elv必须变
                elv[i | (1 << (j-1))] = W - ws[j];
            }
            //如果塞不下,并且结果比之前的一样好
            else if(elv[i] < ws[j] && sts[i | (1 << (j-1))] > sts[i] + 1)
            {
                //一样好 sts无需转移
                //elv 转移为更大的保证最优情况
                elv[i | (1 << (j-1))] = max(W - ws[j], elv[i | (1 << (j-1))]);
            }
        }
    }

    cout << sts[(1 << N) - 1] << endl;
}

int main()
{
    solve();
    return 0;
}
2020/7/12 11:08
加载中...