R - I love sneakers!（分组背包）

淡淡的烟草味﹌ 2022-02-23 03:54 194阅读 0赞

### 题目描述： ###

After months of hard working, Iserlohn finally wins awesome amount of scholarship. As a great zealot of sneakers, he decides to spend all his money on them in a sneaker store.  
![在这里插入图片描述][ef35afe76885c46ac5bbfbb33553acea_v_1554112042]  
There are several brands of sneakers that Iserlohn wants to collect, such as Air Jordan and Nike Pro. And each brand has released various products. For the reason that Iserlohn is definitely a sneaker-mania, he desires to buy at least one product for each brand.  
Although the fixed price of each product has been labeled, Iserlohn sets values for each of them based on his own tendency. With handsome but limited money, he wants to maximize the total value of the shoes he is going to buy. Obviously, as a collector, he won’t buy the same product twice.  
Now, Iserlohn needs you to help him find the best solution of his problem, which means to maximize the total value of the products he can buy.  
Input  
Input contains multiple test cases. Each test case begins with three integers 1<=N<=100 representing the total number of products, 1 <= M<= 10000 the money Iserlohn gets, and 1<=K<=10 representing the sneaker brands. The following N lines each represents a product with three positive integers 1<=a<=k, b and c, 0<=b,c<100000, meaning the brand’s number it belongs, the labeled price, and the value of this product. Process to End Of File.  
Output  
For each test case, print an integer which is the maximum total value of the sneakers that Iserlohn purchases. Print “Impossible” if Iserlohn’s demands can’t be satisfied.  
Sample Input  
5 10000 3  
1 4 6  
2 5 7  
3 4 99  
1 55 77  
2 44 66

Sample Output  
255

##### 题意： #####

第一行给n，m，s  
分别表示有n双鞋，有m钱。这n双鞋需要s种类。  
接下来的n行，分别给出每双鞋的情况。  
a，b，c  
分别表示需要哪个种类。需要多少钱，在主人公心中这双鞋的重要程度。  
问，保证每种类型的鞋最起码选一双。那么重要程度最大会为多少。

分析：  
这其实有点像一个01背包。只不过将只能选一次变成了至少选一次。  
那么， 对于每双鞋来说，他也许是这个种类里面第一次选的， 也有可能是这个种类里面第2次，第三次~~选的。  
所以，状态转移方程为：  
dp\[i\]\[j\]=max（dp\[i\]\[j\]，dp\[i-1\]\[j-v\]+w，dp\[i\]\[j-v\]+w\]）；

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"functional"
    #include"iostream"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    #define scanll(a,b) scanf("%I64d%I64d",&a,&b);
    #define scanl(a) scanf("%I64d",&a);
    #define scanff(a,b) scanf("%lf%lf",&a,&b);
    #define scan1f(a) scanf("%lf",&a);
    #define prinll(a,b) printf("%I64d %I64d",a,b);
    #define prinl(a) printf("%I64d",a);
    #define printff(a,b) printf("%lf %lf",a,b);
    #define printlf(a) printf("%lf",a);
    #define OK printf("\n");
    #define MAXSIXE 10010
    #define INF 100101010
    typedef struct Kind
    {
        ll w;
        ll p;
    } Kind;
    ll dp[21][10010];
    int main()
    {
        ll n,m,s;
        while(~scanf("%lld%lld",&n,&m))
        {
            vector<Kind> kind[21];
            scanl(s);
            for(ll i = 1; i <= n; i ++)
            {
                ll id,a,b;
                scanl(id);
                scanll(a,b);
                kind[id].push_back({a,b});//分类
            }
            memset(dp,0,sizeof(dp));
            for(ll i = 1; i <= s; i ++)
            {
                for(ll j = 0; j < kind[i].size(); j ++)//这种种类里面的鞋都要遍历，同时m也要遍历。
                {
                    for(ll k = m; k >= kind[i][j].w; k --)
                    {
                        dp[i][k] = max(dp[i][k],dp[i][k-kind[i][j].w] + kind[i][j].p);
                        dp[i][k] = max(dp[i][k],dp[i-1][k-kind[i][j].w] + kind[i][j].p);
                    }
                }
            }
            if(dp[s][m] <= 0)
                printf("Impossible\n");
            else
                printf("%lld\n",dp[s][m]);
        }
    }

[ef35afe76885c46ac5bbfbb33553acea_v_1554112042]: https://vj.ti12z.cn/ef35afe76885c46ac5bbfbb33553acea?v=1554112042