洛谷 P1049 装箱问题

链接

https://www.luogu.org/problem/P1049

题目

题目描述

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

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

输入格式

1个整数，表示箱子容量

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

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

输出格式

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

输入输出样例

输入 #1

输出 #1

说明/提示

NOIp2001普及组第4题

思路

01背包问题，还是最标准的那种，借助一下max就行（想动态规划往上面怼的也可以），先输入数据，之后借助二重循环，外层循环是物品的循环，第一件到最后一件，内层循环是重量，从总重量V到物品重量，之后拿总重量减去结果就得到答案。

（动态规划一定不鸽，有空就写—-鸽德）

代码

#include<iostream>

using namespace std;

int main()
{
	int V,n;
	cin>>V>>n;
	int a[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int f[20001]={0};
	for(int i=0;i<n;i++)
	{
		for(int j=V;j>=a[i];j--)
		{
			f[j]=max(f[j],f[j-a[i]]+a[i]);
		}
	}
	cout<<V-f[V];
	return 0;
  }