求noip开心的金明题解！（有答案）

这道题为经典的0-1背包问题，使用动态规划或搜索均可解决。但考虑搜索效率的问题，还是动态规划较好一些。

若用f[i]表示当前用i元能取得的最大收益，w[i]表示物品重要度，p[i]表示物品价格，c[i]:=w[i]*p[i]，则此题中，p为花费，c为收益。动态转移方程为：

f[i]=max{f[i],f[i-p[j]]+c[j]}

在你的标程中，s[i,j]表示在考虑前i件物品且只有j元时所能取得的最大收益。

s[i,j]:=happy((s[i-1,j-v[i]]+v[i]*p[i]),s[i-1,j])

此行程序中，"happy"为判断大小的函数，返回两个参数中较大的一个；买不买第i件物品被讨论。若买了，则要花去v[i]元，获得v[i]*p[i]的收益；若不买，则没有变化，仍然与讨论完上一件物品的情况一样。

s[i,j]取其中较大的一个。

不用数组的话，如何判断一个数不是“快乐数”？

下面的程序以20次变换不能得到1作为判断一个数不是“快乐数”的标准：

#include<iostream>

using namespace std

int happy(int n)

{int s=0,t

for(nn/=10,s+=t*t)

 t=n%10

return s

}

int main()

{ int n,k=0

cin>>n

while(n!=1 &&++k<20)

  n=happy(n)

if(n==1)cout<<"一共变化了"<<k<<"次\n"

else cout<<"不是快乐数\n"

return 0

}

100以内的快乐数一共有20个：

1 一共变化了0次

7 一共变化了5次

10 一共变化了1次

13 一共变化了2次

19 一共变化了4次

23 一共变化了3次

28 一共变化了3次

31 一共变化了2次

32 一共变化了3次

44 一共变化了4次

49 一共变化了4次

68 一共变化了2次

70 一共变化了5次

79 一共变化了3次

82 一共变化了3次

86 一共变化了2次

91 一共变化了4次

94 一共变化了4次

97 一共变化了3次

100 一共变化了1次

---