洛谷 P1049 装箱问题【正难则反/01背包】

题目描述

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

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入输出格式

输入格式：

一个整数，表示箱子容量

一个整数，表示有n个物品

接下来n行，分别表示这n 个物品的各自体积

输出格式：

一个整数，表示箱子剩余空间。

输入输出样例

输入样例#1：

24

6

8

3

12

7

9

7

输出样例#1：

0

说明

NOIp2001普及组第4题

这道题看似是搜索，但是可以用背包做。

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

这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的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 <iostream>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstring>

#include <cstdio>

#include <vector>

using namespace std;

const int maxn = 1e3+5;

const int N = 20005;

#define ll long long

/*

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

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

*/

int t, m, n;

int c[N], v[N], dp[N];

int main()

{

    while(cin >> m >> n)

    {

        for(int i=1;i<=n;i++)

            cin >> v[i];

        memset(dp,0,sizeof(dp));

        for(int i=1; i<=n; i++){

            for(int j=m; j>=v[i]; j--){

                dp[j] = max(dp[j],dp[j-v[i]]+v[i]);

            }

        }

        cout << m-dp[m] << endl; //最小的剩余空间，也就是要求出最大的可装重量

    }

}

巴特西

洛谷 P1049 装箱问题【正难则反/01背包】

最新文章

热门文章