计数型01背包24分求助!!!
查看原帖
计数型01背包24分求助!!!
601747
xibaohe楼主2022/11/12 20:32
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

long long dp[100005]; //dp[j]表示对于前i个砝码,拼成重量为j的方案总数
long long a[100005], cnt; //a[i]表示第i个砝码的重量, cnt表示砝码的个数
int num[7] = {0, 1, 2, 3, 5, 10, 20}; //num[i]表示第i种砝码的重量
int sum, ans; //sum表示所有砝码的重量总和,ans表示所有砝码能拼成的不同重量的个数

int main()
{
	for(int i = 1; i <= 6; i++)
	{
		int x;
		cin >> x; //第i种砝码有x个,每个重量为num[i]
		sum += x * num[i];
		for(int j = 1; j <= x; j++)
			a[++cnt] = num[i];
	}
	
	dp[0] = 1; //拼成重量为0的方案只有一种:一个砝码都不选
	for(int i = 1; i <= cnt; i++)
		for(int j = sum; j >= a[i]; j--)
			dp[j] += dp[j-a[i]];
		
	for(int j = 1; j <= sum; j++)
		if(dp[j] > 0)
			ans++;
	cout<<"Total=";
	cout << ans << endl;
	
    return 0;
}

2022/11/12 20:32
加载中...