苹果

苹果

描述

ctest有n个苹果,要将它放入容量为v的背包。给出第i个苹果的大小和价钱,求出能放入背包的苹果的总价钱最大值。

输入有多组测试数据,每组测试数据第一行为2个正整数,分别代表苹果的个数n和背包的容量v,n、v同时为0时结束测试,此时不输出。接下来的n行,每行2个正整数,用空格隔开,分别代表苹果的大小c和价钱w。所有输入数字的范围大于等于0,小于等于1000。输出对每组测试数据输出一个整数,代表能放入背包的苹果的总价值。样例输入

3 3
1 1
2 1
3 1
0 0

样例输出

2
 
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <list>
#include <memory.h>
#include <string>
#include <math.h>
using namespace std;
  int f[1006][1006];
  int c[1006];
  int w[1006];
  int main()
  {
      int n,v;
    while(cin>>n>>v && n!=0 && v!=0)
    {
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)
        {
            cin>>c[i]>>w[i];
        }
    
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=v;j++)
            {
                f[i][j] = f[i-1][j];
                if(j>=c[i])
            f[i][j] = max(f[i-1][j],(f[i-1][j-c[i]]+w[i]));
            }
        }

        cout<<f[n][v]<<endl;
    }

     return 0;
}

            

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LeetCode

LeetCode <dp>64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left t...

17000
来自专栏青青天空树

成绩大排队

其中姓名和学号均为不超过10个字符的字符串,成绩为0到100之间的一个整数,这里保证在一组测试用例中没有两个学生的成绩是相同的。

8820
来自专栏C语言及其他语言

[每日一题]矩阵问题

今天给大家分享的是二维数组的基本用法,主要是利用数组对行列的控制 题目描述 求一个3×3矩阵对角线元素之和。 输入 矩阵 输出 主对角线 副对角线 元素和 ...

33170
来自专栏NetCore

驳“反驳老赵之“伪”递归”

晚上看到鹤冲天的“反驳老赵之“伪”递归”,大概看了一下,主要是反驳老赵提出的“伪”递归的概念,特别是“伪”,看起来说的都很有道理,但我个人认为,老赵说的没有错,...

22950
来自专栏Vamei实验室

纸上谈兵: 排序算法简介及其C实现

排序的目标是将一组数据 (即一个序列) 重新排列,排列后的数据符合从大到小 (或者从小到大) 的次序。这是古老但依然富有挑战的问题。Donald Knuth的经...

25890
来自专栏C语言C++游戏编程

C语言内置运算符丰富到令人头皮发麻,C语言基础教程之运算符篇

运算符是告诉编译器执行特定数学或逻辑函数的符号。C语言内置运算符丰富,并提供以下类型的运算符 -

13410
来自专栏算法channel

动态规划:括号知多少

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

36770
来自专栏专知

​关关的刷题日记100 – Leetcode 442. Find All Duplicates in an Array

关关的刷题日记100 – Leetcode 442. Find All Duplicates in an Array 题目 Given an array of ...

35960
来自专栏申龙斌的程序人生

零基础学编程028:面向对象编程OOP

在《零基础学编程021:获取股票实时行情数据》一节中,我们想获取6支股票的行情数据,在《零基础学编程022:函数的世界》里我们能够把重复性的代码封装为一个函数p...

31760
来自专栏算法channel

其他|二维指针,数组指针,指针数组

望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。 1c++ c/c++的重要性毋庸置疑,凡是对性能要求很高的系统和算法,其中核...

33450

扫码关注云+社区

领取腾讯云代金券