📗
Notes
  • Introduction
  • Files
  • Android
    • Http
      • Http基础
      • Okhttp理解
    • Jetpack
      • Notes
  • Java ways
    • 101
      • Basis
        • Index
        • Front
          • Angular
            • Angular start 01
            • Angular start 02
          • Typescript
            • Index
            • Ts 01
        • Java
          • Concurrency
          • Frameworks
            • Jdbc与连接池
            • Rxjava基础
            • Spring框架基础
          • Sugar&skill
        • Tool
          • Docker
            • Docker basis
            • Kubernetes play
          • Git
            • Git basic
          • Vim
            • Vim advance
      • Cs
        • Imp
          • Lru
          • Index
    • Snippets
      • Jpa和spring系列注解表
      • Java与oracle数据库各种操作
      • Maven初始化template
      • Nginx配置
      • Nginx反代后配置自动ssl续签
      • 终端033颜色
    • Ways
      • Java ways 01
      • Interview
        • Question
        • Requirements
      • Leetcode101
        • Acwing
          • Index
          • 背包问题
        • Explores
        • Solutions
          • Algorithms
            • Index
          • Concurrency
            • Index
          • Shell
            • Index
          • Sql
            • Index
  • Leecode
    • 牛客
      • 剑指offer
  • Play
    • Youtube离线下载
  • Python basic notes
    • Python days
Powered by GitBook
On this page
  • 背包问题
  • 问题描述
  • Soltion

Was this helpful?

  1. Java ways
  2. Ways
  3. Leetcode101
  4. Acwing

背包问题

PreviousIndexNextExplores

Last updated 4 years ago

Was this helpful?

   Author: Gentleman.Hu
   Create Time: 2020-11-08 12:39:42
   Modified by: Gentleman.Hu
   Modified time: 2020-11-08 13:10:13
   Email: justfeelingme@gmail.com
   Home: https://crushing.xyz
   Description: 对背包问题的探索与学习

背包问题

问题描述

有N件物品和一个容量是V的背包.每件物品只能使用一次.

有i件物品的体积是Vi,价值是Wi.

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大. 输出最大价值.

输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积.

接下来有N行,每行两个整数Vi,Wi,用空格隔开,分别表示第i件物品的体积和价值.

输出格式 输出一个整数,表示最大价值.

数据范围 0<N,V<=1000 0<Vi,Wi<=1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例:

8

Soltion

https://www.acwing.com/problem/content/2/
一维动态规划状态转移方程解释