C++ 01背包

📋 个人简介

💖大家好，我是2022年3月份新人榜排名第三的 ༺Blog༒Hacker༻
🎉支持我：点赞👍+收藏⭐️+留言📝
💬格言：༺永做优质༒programmer༻
📣 系列专栏：CF & UVA🍁
📝 个人主页：༺Blog༒Hacker༻❄️

【问题描述】
有 $N$ 件物品和一个容量为 $V$ 的背包。放入第 $i$ 件物品耗费的空间是 $C_i$ ，得到的价值是 $W_i$ 。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。

【输入格式】
第 $1$ 行两个正整数，分别表示 $N$ 和 $V$ ，中间用一个空格隔开。

第 2 行 $N$ 个正整数，表示 $W_i$ ，中间用一个空格隔开。

第 3 行 $N$ 个正整数，表示 $C_i$ ，中间用一个空格隔开。

其中：$1\le N\le 100$，$1\le V\le 10^6$ ，$1\le C_i\le 10000$，$1\le W_i\le 10000$。

【输出格式】
一行一个正整数，表示最大的价值总和。

【输入样例】

4 20
8 9 5 2
5 6 7 3
1
2
3

【输出样例】

16
1

数据规模与约定
$1\le N\le 100$
$1\le V\le 106$
$1\le C_i\le 10000$
$1\le W_i\le 10000$

💯CODE

#include
using namespace std;
int f[1000005],c[10005],w[10005],n,v;
int main()
{
	cin>>n>>v;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	for(int i=1;i<=n;i++)
		cin>>c[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=v;j>=w[i];j--)
		{
			f[j]=max(f[j],f[j-w[i]]+c[i]);
	    }
	}
	cout<<f[v];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

🔮感谢各位长期以来的支持，点赞收藏是我更新的动力，下期再见，拜拜！！！