dp—完全背包

题目给定一个正整数n，求最少的完全平方数的数量，使他们的和为n。n≤ 60 000

思路：预处理300个完全平方数，假设重量为数值，价值为1，则转化为一个容量为n的完全背包，求最小的价值。由于数值中含有1，则背包一定能装满。

附：完全背包：

普遍形式：dp[i][j]代表前i种物品装在j容量的最大价值，dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i]),k*w[i]<=j

优化：将01背包的逆序改成正序即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

int w[300],dp[60001];
int main(){
	int n;
	for(int i=1;i<300;i++) w[i]=i*i;
	while(~scanf("%d",&n)){
		/*
		for(int i=1;i<300;i++){
			for(int j=v;j>=w[i];j--)
				dp[j]=max(dp[j],dp[j-w[i]]+v[i])
		}
		*/
		memset(dp,0x3f,sizeof(dp));
		dp[0]=0;
		for(int i=1;i<300;i++){
			for(int j=w[i];j<=n;j++)
				dp[j]=min(dp[j],dp[j-w[i]]+1);
		}
		printf("%d\n",dp[n]);
	}
	return 0;
}