蒜头君的购物袋 1

题目：
蒜头君的购物袋 1

代码如下：
二维dp

#include<bits/stdc++.h>
using namespace std;
int dp[35][20005];
int main()
{
	int V,n,v[35];
	cin >> V >> n;
	for(int i = 1;i <= n;i++) cin >> v[i];
	for(int i = 1;i <= n;i++){
		for(int j = 0;j <= V;j++){
			if(j >= v[i]) dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + v[i]);
			else dp[i][j] = dp[i - 1][j];
		}
	}
	cout << V - dp[n][V] << endl;
}

空间压缩后：

*#include<bits/stdc++.h>
using namespace std;
int dp[20005];
int main()
{
	int V,n,v[35];
	cin >> V >> n;
	for(int i = 1;i <= n;i++) cin >> v[i];
	for(int i = 1;i <= n;i++)
		for(int j = V;j >= v[i];j--)
			dp[j] = max(dp[j],dp[j - v[i]] + v[i]);
	cout << V - dp[V] << endl;
	return 0;
}

这道题要求背包最小的剩余空间，因为背包总容量固定，那么就是要求物品能放进背包的最大体积。这道题没有说价值，那么我们可以设定每样物品的价值就是其体积。要求放进背包的最大体积，就是求放进背包的最大价值，那么这道题就是0-1背包问题了。

一开始我想到了二维dp去做，dp[i][j]代表选到前i件物品背包容量为j时获取的最大价值。那么对于第i件物品我们有选和不选两种操作，不选就是dp[i][j] = dp[i - 1][j]，可以理解为此时和选前i - 1件物品所获得的价值相同。选第i件物品就是dp[i][j] = dp[i - 1][j - v[i]] + v[i]，然后每次从中选出二者较大值。

后来想到用一维就可以了，这里用滚动数组来减少空间。

蒜头君的购物袋 1

相关推荐