题目描述
有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积(正整数)。
要求 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
输入格式
第一行是一个整数 V,表示箱子容量。
第二行是一个整数 n,表示物品数。
接下来 n 行,每行一个正整数(不超过10000),分别表示这 n 个物品的各自体积。
输出格式
一个整数,表示箱子剩余空间。
数据范围
0<V≤20000,
0<n≤30
样例
输入样例:
24
6
8
3
12
7
9
7
输出样例:
0
思路一:DP
那么显而易见我们要让物品的体积尽量大,所以体积就是价值。
但是我们选一个物品,首先我们收获了价值,但箱子的体积也相应的减少了容量,所以体积还是价值。
意味着我们在让箱子剩余体积减少时,还能装的容量减少了(怎么这么不通顺)。
那就是01背包了。
只不过这里体积也是价值
时间复杂度 O(n*m)
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 40, M = 10010;
int n, m;
int a[N];
int f[N][M * 2];
//f[i][j]表示考虑前i个物品,总体积不超过j的最大体积。
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
f[i][j] = f[i - 1][j];
//不选当前物品
if (j >= a[i]) f[i][j] = max(f[i][j], f[i - 1][j - a[i]] + a[i]);
//选当前物品,但体积必须足够
}
}
cout << m - f[n][m] << endl; //注意是剩余体积
return 0;
}
//优化
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int f[N];
int n,m;
int main()
{
cin>>m>>n;
memset(f,0,sizeof f);
for (int i = 0; i < n; i ++ )
{
int v;
cin>>v;
for (int j = m; j>=v; j -- )
f[j]=max(f[j],f[j-v]+v);
}
return cout<<m-f[m],0;
}
Java代码
import java.util.*;
import java.io.*;
public class Main{
static int m,n;
static int f[]=new int [100010];
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
m=cin.nextInt();
n=cin.nextInt();
for(int i=0;i<n;i++)
{
int a=cin.nextInt();
for(int j=m;j>=a;j--)
f[j]=Math.max(f[j],f[j-a]+a);
}
System.out.println(m-f[m]);
return ;
}
}
思路二:逆序求最大容量
01背包f[j]表示容量为j的背包最多能装多少价值的物品
而下面的f[j]表示容量为j的背包是否能被装满
能想到这个也是非常nb的
但是这种思路仅限于体积也等同于价值,如果是01背包,这种思路我认为不可行,我没能证明出来
时间复杂度 O(n*m)
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int m,n;
int f[N];
int main()
{
cin>>m>>n;
f[0]=1;
for (int i = 0; i < n; i ++ )
{
int v;
cin>>v;
for (int j = m; j >=v; j --)
f[j]|=f[j-v];
}
for (int j = m; j; j --)
if(f[j])
return cout<<m-j,0;
return 0;
}
Java代码
import java.util.*;
import java.io.*;
public class Main{
static int m,n;
static int f[]=new int [100010];
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
m=cin.nextInt();
n=cin.nextInt();
f[0]=1;
for(int i=0;i<n;i++)
{
int a=cin.nextInt();
for(int j=m;j>=a;j--)
f[j]|=f[j-a];
}
for (int j = m; j>=0; j --)
if(f[j]==1)
{
System.out.println(m-j);
return ;
}
return ;
}
}