求助dp初始条件的小细节
查看原帖
求助dp初始条件的小细节
605777
Jasonde1024楼主2023/10/2 16:45
#include <iostream>
#include <cmath>
using namespace std;

long long counts[7] = {0};
long long dp[1005] = {0};
long long w[7] = {0, 1, 2, 3, 5, 10, 20};

int main() {
	for (long long i = 1; i <= 6; ++i) {
		cin >> counts[i];
      if (counts[i]) dp[i]=1;
	}
	dp[0] = 1;
	long long wsum = counts[1]+2*counts[2]+3*counts[3]+5*counts[4]+10*counts[5]+20*counts[6];
	for (long long i = 1; i <= 6; ++i) { // 砝码种类
		for (long long j = 1; j <= counts[i]; ++j) { // 砝码个数
			for (long long v = wsum; v >= w[i]; --v) {
				dp[v] = max(dp[v], dp[v-w[i]]);
			}
		}
	}
	long long ans = 0;
	for (long long i = 1; i<= wsum; ++i) {
		ans += dp[i];
	}
	cout << "Total=" << ans;
}

其中的dp[v]表示重量v能否用砝码称出。思路和题解区中比较靠前的一篇基本符合,但我们的差别就在于dp初始条件的设置,我的在输入部分多了一行,就是如果存在这个重量的砝码,当然是能够称出来的,所以就把值预先设为1。结果发现运算结果和题解所给代码的结果有很大差别,我不太明白为什么。 求助qwq

2023/10/2 16:45
加载中...