求助QAQ关于完全背包问题
查看原帖
求助QAQ关于完全背包问题
504445
子夜今天AC了么楼主2021/8/4 17:39

a是东西的数量,b是体积,c[i][0]是东西的体积,c[i][1]是东西的重量,要求最小重量

const int inf=0x3f3f3f3f;
int c[103][2], a, b;
int dp[50006];
int sou(int x);
int main() {
	memset(dp, -1, sizeof(dp));
	cin >> a >> b;
	for (int i = 0; i < a; i++) {
		cin >> c[i][0] >> c[i][1];
	}
	cout<<sou(b);
	return 0;
}
int sou(int x) {
	if (dp[x] != -1)
		return dp[x];
	dp[x]=inf;
	for (int i = 0; i < a; i++) {
		if (x >= c[i][0]) {
		dp[x]= min(dp[x], c[i][1] + sou(x - c[i][0]));
		}
	}
	return dp[x] ;//记忆化
}

为什么我这个代码过不了啊QAQ,谢谢大佬

2021/8/4 17:39
加载中...