题意与分析

完全背包问题。
算法背包九讲里面都有提到过，我自己再说下对完全背包的理解。
为什么01背包中遍历状态从VV到00？考虑一下基本方程$dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j])$，如果顺序，那么决定dp[i][j]dp[i][j]的就是dp[i][j−w[i]]dp[i][j−w[i]]而不是dp[i−1][j−w[i]]dp[i−1][j−w[i]]了。

然而，完全背包的方程为dp[i][j]=max{dp[i−1][j−k∗w[i]]+k∗v[i]}dp[i][j]=max{dp[i−1][j−k∗w[i]]+k∗v[i]}。换句话说，在我们考虑第i件物品的时候，我们总是要多一种考虑的情况：再选一件第i个物品。因此，我们需要从dp[i][j−w[i]]dp[i][j−w[i]]推出dp[i][j]dp[i][j]。这样，滚动数组的道理依然成立。

代码

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #define MP make_pair

 #define PB push_back

 #define fi first

 #define se second

 #define ZERO(x) memset((x), 0, sizeof(x))

 #define ALL(x) (x).begin(),(x).end()

 #define rep(i, a, b) for (int i = (a); i <= (b); ++i)

 #define per(i, a, b) for (int i = (a); i >= (b); --i)

 #define QUICKIO                  \

     ios::sync_with_stdio(false); \

     cin.tie();                  \

     cout.tie();

 using namespace std;

 template<typename T>

 T read()

 {

     T tmp; cin>>tmp;

     return tmp;

 }

 int dp[];

 int main()

 {

 QUICKIO

     int T; cin>>T;

     while(T--)

     {

         int e,f; cin>>e>>f;

         int n; cin>>n;

         int w[],v[];

         rep(i,,n)

             cin>>v[i]>>w[i];

         memset(dp,0x3f,sizeof(dp));

         int inf=dp[];

         dp[]=;

         rep(i,,n)

         {

             rep(j,,f-e)

                 if(j>=w[i])

                 {

                     dp[j]=min(dp[j-w[i]]+v[i],dp[j]);

                 }

         }

         if(dp[f-e]==inf) cout<<"This is impossible."<<endl;

         else cout<<"The minimum amount of money in the piggy-bank is "

                  <<dp[f-e]<<".\n";

     }

     return ;

 }

点我看高清美少女

巴特西

「暑期训练」「基础DP」 Piggy-Bank （HDU-1114）

题意与分析

代码

最新文章

热门文章