Knapsack 2

这依旧是一道“典型的dp”
由题意，不难看出这是一道背包dp（01背包）
如往常一样，dp4步走
1：定义状态
以前的dp[i][j]都是表示到第i个物品容量恰好为j的最大总价值是多少，但是这一题中背包容量达到了1e9，数组开不下，怎莫办呢？
很简单，我们只需要把状态稍微一变：dp[i][j]表示到第i个物品总价值恰好为j的最小背包容量，因为用去得背包容量越小，可能装的物品就越多，价值就越大，所以我们要求最小背包容量

2：状态转移方程
以前的01背包都是：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])(w[i]是体积,v[i]是价值)
而现在是:dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])(w[i]是体积,v[i]是价值)

3: 初始化
因为要求最小值（最小背包容量），所以要赋值极大值 memset(dp,0x3f,sizeof(dp)); 而dp[0][0]=1; (由题意，背包容量最小为1)

4：答案
以前我们应该输出dp[n][m]
现在我们要输出价值要循环遍历输出（循环价值去找合法的背包容量），找到最大价值输出

注：本人认为用一维数组滚动优化后更简洁
滚动优化（dp数组去掉第1维，只留下第二维，并且第2层循环倒序遍历）

附上代码：


#include<bits/stdc++.h>
const double PI=acos(-1.0);
using namespace std;
int read(){
	int sum=0,f=1;
	char ch=getchar();
	while (ch<'0' || ch>'9'){
		if (ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while (ch>='0' && ch<='9'){
		sum=sum*10+ch-48;
		ch=getchar();
	}
	return sum*f;
}
void print(int x){
	if (x<0){
		putchar('-');
		x=-x;
	}
	if (x>9){
		print(x/10);
	}
	putchar(x%10+48);
	return;
}
int w[110],v[110];
long long dp[100010];//滚动数组优化 
int main(){
	int n,e;
	cin >> n >> e;//输入 
	int sum=0;
	for (int i=1;i<=n;i++){
		cin >> w[i] >> v[i];//w[i]为体积，v[i]为价值 
		sum+=v[i];//求和 
	}
	memset(dp,0x3f,sizeof(dp));//求最小值赋值最大值 
	dp[0]=0;//初始化 
	for (int i=1;i<=n;i++){//第i个 
		for (int j=sum;j>=v[i];j--){//价值恰好为j （倒序遍历） 
			dp[j]=min(dp[j],dp[j-v[i]]+w[i]);//状态转移方程 
		}
	}
	for (int i=100005;i>=1;i--){//倒序输出（更快） 
		if (dp[i]<=e){//最大价值的合法方案 
			cout << i;//找到就结束 
			return 0;
		}
	}
	return 0;
}

~~~
第一次写AtCoder的题解，请多多指教

文章操作

相关推荐

评论

Knapsack 2