有一个箱子容量为V（正整数， 0 ≤ 𝑉 ≤ 20000 0≤V≤20000），同时有n个物品（ 0 ＜ 𝑛 ≤ 30 0＜n≤30），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

思路

和其他题解一样, 设fi表示在容量i的情况下出现的可能性; 显然取值为0/1(不可能出现/可能出现)

转移方程:

f[i+x] = f[i]  

即: 当前容量存在, 则放x物品之后的容量存在;
可以得出代码:

for(i,1,n)
	for(j,0,v-x[i])
		f[j+x[i]]=f[j];

但不是每个数都可能存在的;
比如在放入8后, 再放入7; 则除了8以外的数都不会存在!

所以可以使用数组优化:

	rep(i,1,n){
        int x;
        read(x);  // 读入当前放入的物品重量
        int len=q.size()-1;  // 枚举已经存在的重量 (ps: 不能使用q.size()来循环! 因为会在循环过程中不断加入数!)
        rep(j,0,len){
            int c=q[j];
            if(c+x<=v&&!vis[c+x]){
                ma=max(c+x,ma);
                vis[c+x]=1;  // 使用vis记录是否存在于队列
                q.push_back(c+x);
            }
        }
    }

完整代码

/*** remain true to the original aspiration ***/
#include<bits/stdc++.h>

using namespace std;

//#pragma GCC optimize(2)
//#pragma G++ optimize(2)

#define pli pair < li , li >
#define ll long long
#define li long long
#define int long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define Test           ll t;read(t); while(t--)
#define pb             push_back
#define all(x)         (x).begin(),(x).end()
#define fi             first
#define se             second
#define Faster         ios_base :: sync_with_stdio( 0 ); cin.tie( 0 ); cout.tie( 0 );
#define YES            printf("YES\n");
#define Yes            printf("Yes\n");
#define NO             printf("NO\n");
#define No             printf("No\n");
int mod=1e9+7;
#define gcd(a, b)     __gcd( a , b )
#define lcm(a, b)     ( a * ( b / gcd( a , b ) ) )
#define popcount(x)    __builtin_popcount(x)
#define string(x)      to_string(x)
int dx[] = {-1, 0, 0, 1};//下左右上
int dy[] = {0, -1, 1, 0};
int dx1[] = {-1, -1, -1, 0, 1, 0, 1, 1, 0};//左下 中下 右下 左 中 右 左上 中上 右上
int dy1[] = {-1, 0, 1, -1, 1, 1, -1, 0, 0};
int dx2[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy2[] = {-1, 1, -2, 2, -2, 2, -1, 1};

const ll INF = 0x3f3f3f3f;
const double PI = 3.141592653589793238462643383279;

ll powmod(ll a, ll b) {
    ll res = 1;
    a %= mod;
    for (; b; b >>= 1) {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

ll square(ll x1, ll y1, ll x2, ll y2) { return abs(x2 - x1) * abs(y2 - y1); }

ll get_dist(ll x1, ll y1, ll x2, ll y2) { return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); }

ll get_jiao(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4) {
    int n1 = max(min(x1, x2), min(x3, x4)), m1 = max(min(y1, y2), min(y3, y4)), n2 = min(max(x1, x2),
                                                                                         max(x3, x4)), m2 = min(
            max(y1, y2), max(y3, y4));
    if (n2 > n1 && m2 > m1)return (n2 - n1) * (m2 - m1); else return 0;
}

template<typename T>
inline bool read(T &x) {
    x = 0;
    int f = 1;
    char c = getchar();
    bool ret = false;
    while (c < '0' || c > '9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c <= '9' && c >= '0') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
        ret = true;
    }
    x = x * f;
    return ret;
}

template<typename T, typename... Args>
inline bool read(T &a, Args &...args) { return read(a) && read(args...); }

template<typename T, typename Type>
inline void print(T x, const Type type) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)print(x / 10, 0);
    putchar(x % 10 ^ 48);
    if (type == 1)putchar(' '); else if (type == 2)putchar('\n');
}

template<typename T, typename Type, typename... Args>
inline void print(T x, const Type type, Args... args) {
    print(x, type);
    print(args...);
}

//#define rint register int
#define rint int
#define rep(i, i0, n)for(rint i=i0;i<=n;i++)
#define per(i, in, i0)for(rint i=in;i>=i0;i--)
#define itn int
#define PII pair<int ,int >
///______________________ L E T ' S  B E G I N _____________________

const int N=1e5+7;
vector<int> q;
int vis[N]={};
signed main() {
    q.push_back(0);
    int n,v;
    read(v);
    read(n);
    int ma=0;
    rep(i,1,n){
        int x;
        read(x);
//        int len=;
        rep(j,0,q.size()-1){
            int c=q[j];
            if(c+x<=v&&!vis[c+x]){
                ma=max(c+x,ma);
                vis[c+x]=1;
                q.push_back(c+x);
            }
        }
    }
    print(v-ma,2);

}


///_______________________ G A M E  O V E R ! ______________________

同类

同样使用这个思想的,还有:

• 2020 CCPC Henan Provincial Collegiate Programming Contest - B. 广告投放