请教一个问题
查看原帖
请教一个问题
206423
焚魂楼主2020/6/23 17:34

初学dp,想问一下这道题为什么这个

for(int j=v;j>=w[i];j--)

一定得从后面开始,而从前面开始就错了呢

谢大佬解答

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int f[20010],n,w[40],v;

void in()
{
	cin>>v;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>w[i];
}

int solve()
{
	for(int i=1;i<=n;i++)
	for(int j=v;j>=w[i];j--)
	{
		if(f[j-w[i]]+w[i]<=v)
		f[j]=max(f[j],f[j-w[i]]+w[i]);
	}
	return f[v];
}

int main()
{
	in();
	cout<<v-solve();
	return 0;
}
2020/6/23 17:34
加载中...