动态规划 – Page 4

HDU 1114 Piggy-Bank

January 26, 20152015-01-26hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <stack>

using namespace std;

struct coinType{
    int w;
    int v;
    coinType(int iv,int iw){
        v = iv;
        w = iw;
    }
};

vector<coinType> coin;
int dp[10005];

int main(){
    int caseCnt;
    cin >> caseCnt;
    while (caseCnt--) {
        int e = 0,f = 0,n = 0;
        cin >> e >> f >> n;

        coin.clear();
        int iv = 0,iw = 0;
        for (int i = 0; i < n; i++) {
            cin >> iv >> iw;
            coin.push_back(coinType(iv,iw));
        }

        int w = f - e;
        memset(dp, 0x3f3f, sizeof(dp));
        dp[0] = 0;
        for (int i = 1; i <= w; i++) {
            for (int j = 0; j < n; j++) {
                if (i < coin[j].w) {
                    continue;
                }
                dp[i]  = min(dp[i-coin[j].w]+coin[j].v,dp[i]);
            }
        }

        if (dp[w] == 0x3f3f3f3f) {
            cout << "This is impossible." << endl;
        }else{
            cout << "The minimum amount of money in the piggy-bank is " << dp[w] << '.' << endl;
        }

    }



    return 0;
}

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

struct coinType{

int w;

int v;

coinType(int iv,int iw){

v = iv;

w = iw;

}

};

vector<coinType> coin;

int dp[10005];

int main(){

int caseCnt;

cin >> caseCnt;

while (caseCnt--) {

int e = 0,f = 0,n = 0;

cin >> e >> f >> n;

coin.clear();

int iv = 0,iw = 0;

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

cin >> iv >> iw;

coin.push_back(coinType(iv,iw));

}

int w = f - e;

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

dp[0] = 0;

for (int i = 1; i <= w; i++) {

for (int j = 0; j < n; j++) {

if (i < coin[j].w) {

continue;

}

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

}

if (dp[w] == 0x3f3f3f3f) {

cout << "This is impossible." << endl;

}else{

cout << "The minimum amount of money in the piggy-bank is " << dp[w] << '.' << endl;

}

return 0;

}

这个基本上还是01背包嘛，但是这回我把状态的判定条件设置为在一定重量的情况下，尽量让硬币的总价值更少。

HDU 2191 悼念512汶川大地震遇难同胞――珍惜现在，感恩生活

January 26, 20152015-01-26hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <stack>

using namespace std;

struct coinType{
    int w;
    int v;
    coinType(int iv,int iw){
        v = iv;
        w = iw;
    }
};

vector<coinType> coin;
int dp[2][105];

int main(){
    int caseCnt;
    cin >> caseCnt;
    while (caseCnt--) {
        int m = 0,n = 0;
        cin >> m >> n;
        coin.clear();

        int maxm = 0;
        for (int i = 0; i < n; i++) {
            int iv = 0,iw = 0,num = 0;
            cin >> iw >> iv >> num;
            maxm += iw*num;
            int factor = 1;
            while (num) {
                if (num >= factor) {
                    num -= factor;
                    coin.push_back(coinType(iv*factor,iw*factor));
                    factor *= 2;
                }else{
                    coin.push_back(coinType(iv*num,iw*num));
                    num = 0;
                }
            }
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 1;i <= coin.size();i++){
            for (int j = 0; j <= m; j++) {
                if(j-coin[i-1].w >= 0)
                dp[i%2][j] = max(dp[(i-1)%2][j-coin[i-1].w]+coin[i-1].v,dp[(i-1)%2][j]);
                else dp[i%2][j] = dp[(i-1)%2][j];
            }
        }
            cout << dp[coin.size()%2][m] << endl;


    }
    return 0;
}

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

struct coinType{

int w;

int v;

coinType(int iv,int iw){

v = iv;

w = iw;

}

};

vector<coinType> coin;

int dp[2][105];

int main(){

int caseCnt;

cin >> caseCnt;

while (caseCnt--) {

int m = 0,n = 0;

cin >> m >> n;

coin.clear();

int maxm = 0;

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

int iv = 0,iw = 0,num = 0;

cin >> iw >> iv >> num;

maxm += iw*num;

int factor = 1;

while (num) {

if (num >= factor) {

num -= factor;

coin.push_back(coinType(iv*factor,iw*factor));

factor *= 2;

}else{

coin.push_back(coinType(iv*num,iw*num));

num = 0;

}

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

for(int i = 1;i <= coin.size();i++){

for (int j = 0; j <= m; j++) {

if(j-coin[i-1].w >= 0)

dp[i%2][j] = max(dp[(i-1)%2][j-coin[i-1].w]+coin[i-1].v,dp[(i-1)%2][j]);

else dp[i%2][j] = dp[(i-1)%2][j];

}

cout << dp[coin.size()%2][m] << endl;

}

return 0;

}

这个是一个多重背包问题，其实多重背包就是01背包，举个例子（其实是扒的）：

¤像如果某件物品的重量为1，价值为2，数量为1000

¤我们就可以拆分成：

¤重量为1，价值为2的物品重量为2，价值为4的物品

¤重量为4，价值为8的物品 …

¤重量为256，价值为512的物品

¤重量为489，价值为489*2的物品

简要地说，就是先拿二进制拆，拆出来1，2，4，8，16，32。。。这样的，等到拆不动了（剩下的不够下一个2进制整幂了），就把剩下的单独拿出来当成一个新物品，这样就不会丢解了。拆分完之后不就变成01背包了嘛。

HDU 2546 饭卡

January 26, 20152015-01-26hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <stack>

using namespace std;

int price[1005];
int dp[2][1100];

int main(){
    int n;
    while (cin >> n && n) {
        memset(price, 0, sizeof(price));
        for (int i = 1; i <= n; i++) {
            cin >> price[i];
        }
        int m;
        cin >> m;
        if (m < 5) {
            cout << m << endl;
            continue;//hehe
        }
        sort(price+1, price+1+n);
        memset(dp, 0xf3f3, sizeof(dp));
        dp[0][0] = 0;
        int res = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= m-5; j++) {
                if(j-price[i]>=0)
                dp[i%2][j] = max(dp[(i-1)%2][j-price[i]]+price[i],dp[(i-1)%2][j]);
                else dp[i%2][j] = dp[(i-1)%2][j];
                res = max(res,dp[i%2][j]);
            }
        }
        cout << m-(res+price[n])  << endl;
    }

    return 0;
}

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

int price[1005];

int dp[2][1100];

int main(){

int n;

while (cin >> n && n) {

memset(price, 0, sizeof(price));

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

cin >> price[i];

}

int m;

cin >> m;

if (m < 5) {

cout << m << endl;

continue;//hehe

}

sort(price+1, price+1+n);

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

dp[0][0] = 0;

int res = 0;

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

for (int j = 0; j <= m-5; j++) {

if(j-price[i]>=0)

dp[i%2][j] = max(dp[(i-1)%2][j-price[i]]+price[i],dp[(i-1)%2][j]);

else dp[i%2][j] = dp[(i-1)%2][j];

res = max(res,dp[i%2][j]);

}

cout << m-(res+price[n]) << endl;

}

return 0;

}

这道题给我玩惨了，原因就是“hehe”那里没有加，后果是啥大家都知道。。。

其实是一个包装过了的01背包问题，既然>=5块时都能随便花，那么我就把最贵的那个留下，然后尽量把饭卡刷到还剩5块钱的程度（不一定是五块，但尽量靠近五块），然后再去买那个最贵的，一次性刷爆。（虽然还是有可能刷不爆的，但余额尽量小是真的），“尽量把饭卡刷到还剩5块钱的程度”，这个就可以转化为重量限定m－5，每个物品重量与价值相等情况下的01背包问题。

就这样。

POJ 3624 Charm Bracelet 顺便讲一下01背包

January 26, 20152015-01-26hahaschoolLeave a comment

#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <stack>

using namespace std;

struct nodeType{
    int w,d;
    nodeType(int iw,int id){
        w = iw;
        d = id;
    }
};

int dp[2][13000];

int main(){
    int n = 0, m = 0;
    while (cin >> n >> m) {
        vector<nodeType> node;
        for (int i = 1; i <= n; i++) {
            int iw = 0,id = 0;
            cin >> iw >> id;
            node.push_back(nodeType(iw,id));
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j-node[i-1].w >= 0) {
                    dp[i%2][j] = max(dp[(i-1)%2][j-node[i-1].w]+node[i-1].d, dp[(i-1)%2][j]);
                }else{
                    dp[i%2][j] = dp[(i-1)%2][j];
                }
            }
        }
        cout << dp[node.size()%2][m] << endl;
    }

    return 0;
}

#include <iostream>

#include <sstream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <stack>

using namespace std;

struct nodeType{

int w,d;

nodeType(int iw,int id){

w = iw;

d = id;

}

};

int dp[2][13000];

int main(){

int n = 0, m = 0;

while (cin >> n >> m) {

vector<nodeType> node;

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

int iw = 0,id = 0;

cin >> iw >> id;

node.push_back(nodeType(iw,id));

}

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

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

for (int j = 0; j <= m; j++) {

if (j-node[i-1].w >= 0) {

dp[i%2][j] = max(dp[(i-1)%2][j-node[i-1].w]+node[i-1].d, dp[(i-1)%2][j]);

}else{

dp[i%2][j] = dp[(i-1)%2][j];

}

cout << dp[node.size()%2][m] << endl;

}

return 0;

}

裸的01背包问题，是DP的基础题型了，没有太多好说的。

简要说一下01背包问题的状态转移特点：按两个基准纪录数据，第一个基准是我们从0～a号物品中选，第二个基准是选择的物品已经有了多少重量b，这样组成了dp数组dp[a][b]，这个数组存储的是当前状态的价值是多少。接下来我们开始dp，对于每一个当前状态（最多选择到第n个物品，已经占用了w重量），我们是从两种先前状态中导出的：1.最多选择到n－1个物品（就是当前物品还没有考虑呢），占用重量w－x（x是第n个物品重量），在这个状态上，我们添加上第n个物品。2.最多选择到n－1个物品，占用重量w，在这个状态上，我们什么也不做，直接把他当成当前状态。

在这两种先前状态中选择最好的那个（有时候因为某些原因，只能选择一个，那就选唯一的那个就好），保存下来决定为当前状态，再供以后使用。

这样我们只要读取dp[i][j]的值，就是“选择1～i中的物品，重量限定为j，最高价值是？”这个问题的答案。（没有用滚动数组的话）