首页 > 代码库 > hdu1114

hdu1114

2024-11-17 02:42:01   202人阅读

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

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

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

技术分享
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <string>#include <cstdlib>#define Maxn 0xfffffffusing namespace std;int cmp(int x,int y){    return x < y?x:y;}//int dp[1100][1100];int v[11000];int w[11000];int dp[11000];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 = 1;i <= n;i++){            cin >> v[i] >> w[i];        }        for(int i = 0;i <= V;i++)            dp[i] = Maxn;        dp[0] = 0;        for(int i = 1;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 0;}
View Code

 

hdu1114


联系
我们