hdu1114

时间:2022-04-05 08:01:26

完全背包的水题,不过今天才学动态规划,就这样啦……hahahah!!!

完全背包跟普通背包的区别是普通背包从后往前循环,以防止被替换

完全背包是从前往后循环,后面的状态会跟着之前状态的改变而改变……

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#define Maxn 0xfffffff using namespace std; int cmp(int x,int y){
return x < y?x:y;
} //int dp[1100][1100];
int v[];
int w[];
int dp[]; int main()
{
// freopen("input.txt","r",stdin);
int t;
cin >> t;
while(t--){
int M;
int V,n;
cin >> M >> V;
V -= M;
cin >> n;
for(int i = ;i <= n;i++){
cin >> v[i] >> w[i];
}
for(int i = ;i <= V;i++)
dp[i] = Maxn;
dp[] = ;
for(int i = ;i <= n;i++){
for(int j = w[i];j <= V;j++){
dp[j] = cmp(dp[j],dp[j-w[i]]+v[i]);
}
}
if(dp[V] == Maxn)
cout << "This is impossible." << endl;
else
cout << "The minimum amount of money in the piggy-bank is " <<dp[V] <<"."<< endl;
}
return ;
}