Brief description :

要求每类物品至少选择一个的0/1背包。

Analyse :

… 今天集训队放假，因此比较有时间复习几道之前比赛时没有写出的题目，首先是这道背包题，因为之前有收集8姐的源码。

#include 
#include 
#include 

using namespace std;
const int N = 100, M = 10001, K = 10;
const int INF = 1e9;
struct snearker{
    int price, value;
};
vector s[K];
int d[2][M], g[M];
int n, m, k, p, q;
int ans;
// d: 考察前i种商品, 分配j块钱时所能取得的最大值。(每种商品都要选否则赋值为-INF.)
// g: 只考察第i组商品， 分配j块钱时所能取得的最大值，如果无法购买任何一个则记作0。。



void init(){
    int index; snearker x;
    for (int i=0;i> index >> x.price >> x.value;
        s[index-1].push_back(x);
    }
}

void solve(){

    ans = -1;
    for (int i=0;i=s[i][j].price;k--){
                if (g[k-s[i][j].price]==-1) continue;
                g[k] = max(g[k], g[k-s[i][j].price] + s[i][j].value);
            }
        q = p; p = 1 - p;
        memset(d[p], -1, sizeof(d[p]));

        for (int k=1;k<=m;k++){
            if (g[k]==-1) continue;
            for (int j=k;j<=m;j++){
                if (d[q][j-k]==-1) continue;
                d[p][j] = max(d[p][j], d[q][j-k] + g[k]);
            }
        }
    }

    for (int i=1;i<=m;i++){
        if (d[p][i]==-1) continue;
        ans = max(ans, d[p][i]);
    }


}

int main(){
    while (cin >> n >> m >> k){
        init(); solve();
        if (ans==-1) printf("Impossible\n");
        else printf("%d\n", ans);
    }
}

#include 
#include 
#include 

using namespace std;
const int N = 101, M = 10001, K = 11;
struct snearker{
    int price, value;
    int type;
    friend bool operator <(snearker a, snearker b){
        return a.type> s[i].type >> s[i].price >> s[i].value;
        c[s[i].type] = true;
    }

    sort(s, s+n);
}

void solve(){
    ans = -1;
    for (int i=1;i<=k;i++) if (!c[i]) return;

    memset(d[0], -1, sizeof(d[0])); d[0][0] = 0;
    //memset(d[0], 0, sizeof(d[0]));
    p = 0;

    for (int i=0;i=s[i].price;j--){
            if (d[p][j-s[i].price]!=-1)
                d[p][j] = max(d[p][j], d[p][j-s[i].price] + s[i].value);
            if (d[q][j-s[i].price]!=-1)
                d[p][j] = max(d[p][j], d[q][j-s[i].price] + s[i].value);
        }
    }



    for (int i=1;i<=m;i++){
        if (d[p][i]==-1) continue;
        ans = max(ans, d[p][i]);
    }
    //ans = d[p][m];
}

int main(){
    while (cin >> n >> m >> k){
        init(); solve();
        if (ans==-1) printf("Impossible\n");
        else printf("%d\n", ans);
    }
}

Note :

这题确实存在这两种方法，第一种是先将物品进行分组，进行一次0/1背包，再将之后得到的 g 数组取出做为物品进行第二次0/1背包。。。
比赛的时侯没有写完。。之后提交的时侯则一直 TLE 。。。。
第二种代码则是阅读8姐的方法以后写出的。。。是一种更直接的动态规划，可以在时限内 AC。

1. 边界条件

在阅读了8姐的码之后我发现之前在这里的处理实际上是比较乱的。。而且我认为必须把数组赋初值－1，（这样才能保证得到如果一个类别的物品没有取则不能得到解。。）并且再结束动态规划之后要在整个数组里扫描一遍以取出最大值。。
但是8姐的代码也是对的，关于这题里什么时侯赋－1，什么时侯赋 0 也是一个很值得思索的问题。

2. 飘逸的排序。
8姐的码里的那个排序写的很飘逸。。。
我在阅读之后还自己yy了一个重载小于号为 a.ty!=b.ty 的方法，想排出 1 1 3 2 2 2 这种神奇的效果，不过失败。～
我还是写普通的吧～

3. 进一步的优化。
关于第一个代码的TLE我是有很多不满的。。而且具体原因也没有办法找到，但是值得肯定的是分组进行两次动态规划一定有它的好处的。。。
。。。（比如每层的物品数会减少，有效的状态会有限。。但我不知道如何应用这个特性进行优化，是否要用双向链表保存状态，但我不能确定会有效。。。。）

Posted by xiaodao
Category: 日常