http://acm.hdu.edu.cn/showproblem.php?pid=2126
题意：给你n种物品以及每种物品的价格，m的钱，问你在满足买最多种物品的前提下，有多少种不同的够买方案
解法1：
首先献上我的比较挫的方法，也是大众化的方法，dp[i][j][k]表示前i种物品，买了j个，花了小于等于k的钱的时候的方案数
因为是小于等于k，所以初始化的时候要注意哦。
那么转移的时候第i种物品取或者不取
dp[i][j][k]+=dp[i-1][j-1][k-p[i]]; dp[i][j][k]+=dp[i-1][j][k];
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[35][35][510];
int p[35];
int main()
{
int t,m,n;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
memset(dp,0,sizeof(dp));
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
dp[i][0][j]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
for(int k=m;k>=0;k--)
{
if(k>=p[i]) dp[i][j][k]+=dp[i-1][j-1][k-p[i]];
dp[i][j][k]+=dp[i-1][j][k];
// printf("i=%d j=%d k=%d %d\n",i,j,k,dp[i][j][k]);
}
}
}
int ops=-1,kinds=-1;
for(int i=n;i>=1;i--)
{
for(int j=i;j>=1;j--)
{
for(int k=m;k>=0;k--)
{
if(dp[i][j][k])
{
//printf("%d %d %d\n",i,j,k);
kinds=j;
ops=dp[i][j][k];
break;
}
}
if(kinds!=-1) break;
}
if(kinds!=-1) break;
}
if(ops!=-1)
{
printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",ops,kinds);
}
else printf("Sorry, you can't buy anything.\n");
}
return 0;
}
解法二：直接变成rank2了！！！
其实也很简单，可以这样设计状态开一个dp[30][500][2]的数组，dp[i][j][0]就表示前i个物品，花了 <= j 的钱，最多可以买到的纪念品数量，dp[i][j][1]就表示买到最多纪念品前提下的方案数了，转移的时候就按照关键字来转移，
先判断能否增加所买的纪念品的种类数，
再判断种类数相同的时候的情况
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[31][501][2];
int v[31];
int main()
{
int t,m,n;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
memset(dp,0,sizeof(dp));
for(int i=0;i<=m;i++) dp[0][i][1]=1;
for(int i=0;i<=n;i++) dp[i][0][1]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<v[i];j++) dp[i][j][0]=dp[i-1][j][0],dp[i][j][1]=dp[i-1][j][1];
for(int j=v[i];j<=m;j++)
{
if(dp[i-1][j-v[i]][0]+1>dp[i-1][j][0])
{
dp[i][j][0]=dp[i-1][j-v[i]][0]+1;
dp[i][j][1]=dp[i-1][j-v[i]][1];
}
else if(dp[i-1][j-v[i]][0]+1==dp[i-1][j][0])
{
dp[i][j][0]=dp[i-1][j][0];
dp[i][j][1]=dp[i-1][j][1]+dp[i-1][j-v[i]][1];
}
else
{
dp[i][j][0]=dp[i-1][j][0];
dp[i][j][1]=dp[i-1][j][1];
}
}
}
if(dp[n][m][0]) printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",dp[n][m][1],dp[n][m][0]);
else printf("Sorry, you can't buy anything.\n");
}
return 0;
}
解法三：rank1
优化是永无止境的~ 突然发现只有最后一层的状态有用，那就用滚动数组试试吧
结果，直接跑到了rank1
精益求精，截图留念一下
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[501][2], v[31];
int main()
{
int t,m,n;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
memset(dp,0,sizeof(dp));
for(int i=0;i<=m;i++) dp[i][1]=1;
for(int i=1;i<=n;i++)
{
dp[0][1]=1;
for(int j=m;j>=v[i];j--)
{
if(dp[j-v[i]][0]+1>dp[j][0])
{
dp[j][0]=dp[j-v[i]][0]+1;
dp[j][1]=dp[j-v[i]][1];
}
else if(dp[j-v[i]][0]+1==dp[j][0])
{
dp[j][1]=dp[j][1]+dp[j-v[i]][1];
}
}
}
if(dp[m][0]) printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",dp[m][1],dp[m][0]);
else printf("Sorry, you can't buy anything.\n");
}
return 0;
}
还有些人竟然可以用0kb的内存，- -！，难道是纯数学方法？