P1049装箱问题

HRLYB · 2019-04-02 17:05:36 · 个人记录

P1049装箱问题

这一道题，我乍一看没啥思路，只好去翻题解

好在题解讲的详细，使我了解了神奇的

01背包

题目要求求出最小的剩余空间，也就是要求出最大的可装重量

这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的01背包问题：

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）和一个价值（等于体积）。

要求n个物品中，任取若干个装入箱内，使总价值最大。

对于每一个物体，都有两种状态：装与不装

那么，对于任意重量m的最大价值 f (m) = max ( f ( m - w[i] ) + w[i], f (m) )（w为重量（即价值））

其中，f ( m - w[i] ) 指在装了物品i后，箱子的剩余容量能装的最大重量

f ( m - w[i] ) + w[i] 指在在装了物品i后，箱子能装的最大重量

#include<bits/stdc++.h>
using namespace std;
int v,n,a[105],f[21000];//最多20000种质量（箱子容量小于20000）
int main(){
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
        for(int j=v;j>=a[i];j--)
        f[j]=max(f[j-a[i]]+a[i],f[j]);
    printf("%d\n",v-f[v]);
    return 0;
}