『求助』分析动态规划题目如何解 [复制链接]

哪位大牛帮我分析一下如何解决用DP解决计数问题嘛！！
就利用这道题目来分析嘛：

设有1G，2G，3G，5G，10G，20G的砝码各若干（其总重量《=1000G）
输入：A1，A2，。。，A6（表示1G有A1个，2G有A2个……）
输出：能称出的不同重量的个数！ （不包括一个砝码都不用的情况）

谢谢了呀！！

一开始
f[0]:=true;
f[k]=true 表示 kG能称出来
for i:=1 to max do
  对于所有的f=true 都有 f[i+1]=ture;{砝码是一}
for i:=1 to max do
  对于所有的f=true 都有 f[i+2]=ture;{砝码是二}
for i:=1 to max do
  对于所有的f=true 都有 f[i+3]=ture;{砝码是三}
for i:=1 to max do
  对于所有的f=true 都有 f[i+5]=ture;{砝码是五}
for i:=1 to max do
  对于所有的f=true 都有 f[i+10]=ture;{砝码是十}

编程的时候用滚动数组。
如果砝码以有两的，就对砝码一的情况做两次。

什么东西哦？？怎么理解不到呢？？

请具体讲一下怎么用动态规划解决计数问题哦!!??

下面是引用tangyouze于2005-11-05 17:00发表的:
一开始
f[0]:=true;
f[k]=true 表示 kG能称出来
for i:=1 to max do
  对于所有的f=true 都有 f[i+1]=ture;{砝码是一}
.......

请问有没有一条完整的程序帮助理解？？？

....这个明显是动态规划
#include <stdio.h>

int main( )
{
int a[ 6 ], m[ 6 ], total = 0, i, j, k, f[ 1001 ];
for ( i = 0; i <= 1000; i++ )
f[ i ] = 0;
f[ 0 ] = 1;
m[ 0 ] = 1; m[ 1 ] = 2; m[ 2 ] = 3; m[ 3 ] = 5; m[ 4 ] = 10; m[ 5 ] = 20;
for ( i = 0; i < 6; i++ )
scanf("%d", &a[ i ]);
for ( i = 0; i < 6; i++ )
{
for ( j = 0; j < a[ i ]; j++ )
{
for ( k = 1000; k >= m[ i ]; k-- )
if ( f[ k - m[ i ] ] && !f[ k ] )
{
f[ k ] = 1;
total++;
}
}
}
printf("Total=%d\n", total);
return 0;
}

背包问题。