题意与分析
完全背包问题。
算法背包九讲里面都有提到过，我自己再说下对完全背包的理解。
为什么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]。这样，滚动数组的道理依然成立。
代码
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #define MP make_pair 6 #define PB push_back 7 #define fi first 8 #define se second 9 #define ZERO(x) memset((x), 0, sizeof(x)) 10 #define ALL(x) (x).begin(),(x).end() 11 #define rep(i, a, b) for (int i = (a); i <= (b); ++i) 12 #define per(i, a, b) for (int i = (a); i >= (b); --i) 13 #define QUICKIO 14 ios::sync_with_stdio(false); 15 cin.tie(0); 16 cout.tie(0); 17 using namespace std; 18 19 template<typename T> 20 T read() 21 { 22 T tmp; cin>>tmp; 23 return tmp; 24 } 25 int dp[10005]; 26 int main() 27 { 28 QUICKIO 29 int T; cin>>T; 30 while(T--) 31 { 32 int e,f; cin>>e>>f; 33 int n; cin>>n; 34 int w[505],v[505]; 35 rep(i,1,n) 36 cin>>v[i]>>w[i]; 37 memset(dp,0x3f,sizeof(dp)); 38 int inf=dp[0]; 39 dp[0]=0; 40 rep(i,1,n) 41 { 42 rep(j,0,f-e) 43 if(j>=w[i]) 44 { 45 dp[j]=min(dp[j-w[i]]+v[i],dp[j]); 46 } 47 } 48 if(dp[f-e]==inf) cout<<"This is impossible."<<endl; 49 else cout<<"The minimum amount of money in the piggy-bank is " 50 <<dp[f-e]<<". "; 51 } 52 return 0; 53 }