首页 > 编程学习 > 让人头疼的“双十一”

让人头疼的“双十一”

发布时间:2022/11/18 12:20:18

双十一就这样轰轰烈烈的来了,网购宅男小明磨拳霍霍!理想是丰满的,现实是骨感的。小明虽然在购物车添加了不少物品,但是他低头看了下口袋却是叹声连连。小明想要购买的商品中,每件商品都有其价格和期待值,小明只能利用有限的资金,购买能让自己期待值总和达到最大的一系列物品了。

输入格式:

第一行一个整数T表示有T组测试数据(T<=50)。

接下来的T组测试数据:

第一行包含两个整数N和M,N表示小明有多少钱,M表示有多少件物品(1<=M<=100)。

再二行包含M个整数,表示对应每个物品的价格。

第三行包含M个整数,表示小明对每个物品的期待值。

其中,小明兜里的钱N、每个物品的价格、每个物品的期待值的值域均为(0, 3000)。

输出格式:

每组样例一行,输出最大期待值的总和。假设第i组样例最大期待值为e,则输出格式为“Case #i: e”

输入样例:

4
10 5
2 3 7 7 3
4 3 5 6 4
10 8
5 6 4 2 3 7 1 8
5 3 5 3 5 7 5 7
20 7
10 15 4 5 6 8 5
15 14 9 2 2 6 7
10 3
7 4 5
16 7 10

输出样例:

Case #1: 11
Case #2: 18
Case #3: 31
Case #4: 17

h0173. 01背包问题_星河欲转。的博客-CSDN博客 

//这里不能用贪心算法,可以参考上面这个链接,其中还有另一个详细链接,希望对大家有所帮助,代码没问题,如果本人理解和阐述有问题,请大家提出

#include<bits/stdc++.h>
using namespace std;
struct xx{
    int w,v;
}s[105];//这里用数组也可以
int main(){
    int n,m,i,j,t,x=1,a[3005];
    cin>>t;
    while(t--)
   { cin>>m>>n;
   memset(a,0,sizeof(a));//数组初始化,也可以直接a[3005]={0};
    for(i=0;i<n;i++)
        cin>>s[i].w;
         for(i=0;i<n;i++)
        cin>>s[i].v;
    for(i=0;i<n;i++)
        for(j=m;j>=s[i].w;j--)
            a[j]=max(a[j],(a[j-s[i].w]+s[i].v));
       printf("Case #%d: %d\n",x++,a[m]);
    }
   
    return 0;

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式