问题标题: 酷町堂：3321 背包问题

3321   背包问题

经验值：1200 时间限制：1000毫秒

题目描述 Description

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

输入描述 Input Description

1个整数，表示箱子容量

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

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

输出描述 Output Description

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

样例输入 Sample Input

24 6 8 3 12 7 9 7

样例输出 Sample Output

0

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, c;
int w[50000];
int f[5000][5000];
int dfs(int n, int c) {
	if (f[n][c] != -1) {
		return f[n][c];
	}
	if (n == 0 || c == 0) {
		return 0;
	}
	if (w[n] > c) {
		return f[n][c] = dfs(n - 1, c);
	}
	else {
		return f[n][c] = max(dfs(n - 1, c), dfs(n - 1, c - w[n]) + w[n]);
	}
}
int main() {
//	freopen ("题目名.in", "r", stdin);
//	freopen ("题目名.out", "w", stdout);
	memset(f, -1, sizeof(f));
	cin >> c >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> w[i];
	}
	cout << c - dfs(n, c);
//	fclose (stdin);
//	fclose (stdout);
	return 0;//好习惯！
}

90分，这种题比走迷宫还要ex

张恩泽在2021-06-17 19:02:51追加了内容

我再顶！！

张恩泽在2021-06-17 19:09:16追加了内容

各位大佬看一看啊！！

感激不尽