首页 > 其他分享 >acwing 二维费用的背包问题

acwing 二维费用的背包问题

时间:2022-10-17 22:55:56浏览次数:79  
标签:输出 背包 int 重量 二维 件物品 10010 acwing

题面
有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。

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

输入格式
第一行三个整数,N,V,M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行,每行三个整数 vi,mi,wi,用空格隔开,分别表示第 i 件物品的体积、重量和价值。

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

数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例:
8

#include<bits/stdc++.h>
using namespace std;

int v[10010],w[10010],m[10010],f[10010][10010],V,M,n;

int main(){
	cin>>n>>V>>M;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>m[i]>>w[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=V;j>=v[i];j--)
			for(int k=M;k>=m[i];k--)
				f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
	cout<<f[V][M];
}

标签:输出,背包,int,重量,二维,件物品,10010,acwing
From: https://www.cnblogs.com/Nikkie-02/p/16801055.html

相关文章

  • 01背包问题
    题面有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是vi,价值是wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价......
  • 2022下半年 Acwing 第一篇:快排模板
    模板内容:C++voidquick(intq[],intl,intr){if(l>=r)return;intx=q[(l+r+1)>>1],i=l-1,j=r+1;while(i<j){doi++;while(q[i]<x);......
  • 二维数组作为形参的几种调用方法
    1、/将二维数组看做一维数组进行处理(在栈上进行处理)/voidfunc1(intarr,introw,intcol){inti=0,j=0;printf("子函数打印:\n");for(i=0;i<row;i++){......
  • python学习记录:简单二维码生成器源码
     Function:  二维码生成器Author:  琴棋书画'''importioimportsysimportqrcodefromPyQt5importQtWidgets,QtGuifromPyQt5.QtWidgetsimportQA......
  • leetcode-240. 搜索二维矩阵 II --z字搜索
    240.搜索二维矩阵IIZ字搜索法,持续缩小target可能在的范围,从右上角进入矩阵开始搜索,左下角也是一样的,但是不能从左上角或右下角开始范围:x再大也不能超过矩阵宽度,y......
  • 页面缩放, 相对定位的二维码等比例缩放,始终出现在正确位置
    前几天做了一个简单的页面,如下:要求:随着页面缩放二维码的位置要在正确的位置上,搞了两三个小时,没搞定,第二天重新规划结构,5分钟完成,已此记下来这个教训,<!DOCTYPE......
  • 消除游戏的格子的index和二维数组row-column的换算
       index = row x MaxColumn + col            // 一个5x4的矩阵的index            // 0,1,2,3,            //......
  • 动态规划 完全背包问题
     完全背包问题与简单背包问题最为明显的区别就是,每件物品可以无限次使用,也就是说,你的背包可以只装这一件物品下面附上题解/*f[g]代表当背包空间为g的时候,背包的最......
  • AcWing1251 打击罪犯--并查集
    #include<bits/stdc++.h>#definepbpush_back#definefifirst#definesesecond#defineall(x)(x).begin(),(x).end()#defineSZ(x)(int)(x).size()usingnam......
  • AcWing 4706 -- 树形DP/DFS
    题目描述4706.最短路程思路dfs代码#include<iostream>#include<cstring>#include<algorithm>#include<vector>usingnamespacestd;constintN=100......