Money Systems

分析：来看看背包九讲里面的一段话：

对于一个给定了背包容量、物品费用、物品间相互关系(分组、依赖等) 的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。例如若每件物品均是完全背包中的物品，转移方程即为：

dp[i][j]=dp[i-1][j]+dp[i-1][j-v[i]]，因为必须是由这两个状态转换过来的，边界是dp[0][0]=1，所以这道题的代码如下

 #include "iostream"

 #include "cstdio"

 #include "cstring"

 #include "string"

 using namespace std;

 const int maxn=1e6+;

 int n,V;

 int a[];

 long long dp[maxn];

 int main()

 {

     cin>>n>>V;

     for(int i=;i<=n;i++)

         cin>>a[i];

     dp[]=;

     for(int i=;i<=n;i++)

         for(int j=a[i];j<=V;j++)

             dp[j]=dp[j]+dp[j-a[i]];

     cout<<dp[V]<<endl;

 }

巴特西

Money Systems

最新文章

热门文章