完全背包问题

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxs 110

#define maxb 10

#define maxn 10

int s,n[maxs],c[maxs][maxn],k[maxs][maxn],p[maxs];

int b,cbuy[maxb],kbuy[maxb],pbuy[maxb];

int tmp[10];

int dp[100000];

int maxindex;

map<int,int> ys;

void dfs1(int myindex,int dep,int cost){

    if(dep==b+1){

        maxindex=max(maxindex,myindex);

        dp[myindex]=cost;

        return;

    }

    for(int i=0;i<=kbuy[dep];i++){

        dfs1(myindex*10+i,dep+1,cost+i*pbuy[dep]);

    }

}

void init(){

    dfs1(0,1,0);//初始化dp数组

}

int mici(int di,int zhi){

    int ret=1;

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

        ret*=di;

    }

    return ret;

}

void dfs(int num,int dep,int cost,int x){

    if(dep==b+1){

        dp[num]=min(dp[num],dp[num-x]+cost);

        return;

    }

    for(int i=tmp[dep];i<=kbuy[dep];i++){

        dfs(num*10+i,dep+1,cost,x);

    }

}

int main(){

    scanf("%d",&s);

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

        scanf("%d",&n[i]);

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

            scanf("%d%d",&c[i][j],&k[i][j]);

        }

        scanf("%d",&p[i]);

    }

    scanf("%d",&b);

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

        scanf("%d%d%d",&cbuy[i],&kbuy[i],&pbuy[i]);

        ys[cbuy[i]]=i;

    }

    //以上是输入

    init();

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

        int tmpindex=0;

        bool flag=1;

        memset(tmp,0,sizeof(tmp));

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

            if(ys.find(c[i][j])!=ys.end()){//如果这种商品是所需要买的商品

                if(kbuy[ys[c[i][j]]]<k[i][j]){//如果这种商品的需求量小于该种

                //采购方案所列的购买量

                    flag=0;

                    break;

                }

                else{

                    tmp[ys[c[i][j]]]=k[i][j];//这种商品的所列的购买量

                    tmpindex+=k[i][j]*mici(10,b-ys[c[i][j]]);

                }

            }

            else{

                flag=0;

                break;

            }

        }

        if(!flag)continue;//这种采购方案根本用不了

        dfs(0,1,p[i],tmpindex);//其实是dp层数b在写程序时未定，所以不适合写for循环罢了

    }

    //以下是输出部分

    printf("%d",dp[maxindex]);

    system("pause");

    return 0;

}