正文 

当前位置： 首页 > java > java框架

01背包

phlsheji      2022-02-16     316

关键词： 

<span style="color:#3333ff;">/*
__________________________________________________________________________________________________
*     copyright:   Grant Yuan                                                                     *
*     algorithm:   01背包                                                                       *
*     time     :   2014.7.18                                                                      *
*_________________________________________________________________________________________________*
F - 01背包
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit
 
Status
Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave … 
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
 


 
Input
The first line contain a integer T , the number of cases. 
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
 
Output
One integer per line representing the maximum of the total value (this number will be less than 2 31).
 
Sample Input
 1
5 10
1 2 3 4 5
5 4 3 2 1 
 
Sample Output
 14 
 */
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<cstdlib>
using namespace std;

int v[1001];
int p[1001];
int n,sv,t;
int dp[2][1001];

int main()
{
	cin>>t;
	while(t--){
	  cin>>n>>sv;
	  for(int i=0;i<n;i++)
		  cin>>p[i];
	  for(int i=0;i<n;i++)
		  cin>>v[i];
	  memset(dp,0,sizeof(dp));
	  for(int i=0;i<n;i++)
		 for(int j=0;j<=sv;j++)
	  {
	  	if(j<v[i])
			  dp[(i+1)&1][j]=dp[i&1][j];
	    else
			  dp[(i+1)&1][j]=max(dp[i&1][j],dp[i&1][j-v[i]]+p[i]);

	  }
	  cout<<dp[n&1][sv]<<endl;
	}
	return 0;
}
</span>

背包问题（01背包，完全背包，多重背包）

...http://www.cnblogs.com/daoluanxiaozi/archive/2012/05/06/2486105.html 背包问题，经典有背包九讲。01背包 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些... 查看详情

01背包，完全背包，多重背包，混合背包

详见大牛背包九讲(下载地址：http://pan.baidu.com/s/1b9edXW)1//Class->物品种类，val->价值，room->所占空间，num->物品数量，Room->背包容量23#include<stdio.h>4constintmaxn=1e6;56intbag[maxn];7intRoom;89voidzero_one_bag( 查看详情

动态规划_01背包_完全背包_多重背包_分组背包(代码片段)

目录动态规划问题结题思路：模板题链接：01背包思路：代码：完全背包思路:代码多重背包思路：代码：组合背包思路：代码：动态规划问题结题思路：模板题链接：01背包模板题完全背包... 查看详情

01背包两维背包

#include<iostream>#include<algorithm>usingnamespacestd;/********************************01背包*/#defineN5#defineM12intvalue[N+1]={0,6,3,5,4,6};intweight[N+1]={0,2,2,6,5,4};//#defineN5//#defi 查看详情

动态规划之背包问题-01背包+完全背包+多重背包(代码片段)

01背包有n种不同的物品，每种物品分别有各自的体积v[i]，价值 w[i] 现给一个容量为V的背包，问这个背包最多可装下多少价值的物品。1for(inti=1;i<=n;i++)2for(intj=V;j>=v[i];j--)3dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//dp[V]为所求完全背包0... 查看详情

动态规划背包问题01背包完全背包多重背包

 一、01背包有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。这是最基础的背包问题，总的来说就... 查看详情

动态规划-01背包

...，学长们很早之前就讲过了，然而我现在才来写。。。01背包01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。01背包题目的雏形是：有N件物品和一个容量为V的... 查看详情

01背包完全背包多重背包

参考（都有些错误）：https://github.com/guanjunjian/Interview-Summary/blob/master/notes/algorithms/%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/01%E8%83%8C%E5%8C%85.mdhttps://blog.csdn.net/na_beginning/article/details/6 查看详情

9大背包第一弹|01背包

今天学习01背包。因为01背包在暑假学习过，所以上网看了一下文章，就能写出来了。主要还是一种动态规划的思想，设置背包的【容量】进行增长，【物品】进行增长。只要满足【当前物品】的【价值】=ｍａｘ｛　　　　　　... 查看详情

01背包java实现（入门到精通）

一、什么是01背包　　01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品，每种物品有且只有一... 查看详情

01背包+滚动数组

01背包定义：在$M$件物品取出若干件放在空间为$V$的背包里，每件物品的体积为$V_1$，$V_2$至$V_n$，与之相对应的价值为$W_1$，$W_2$至$W_n$。01背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。... 查看详情

01背包

问题描述：给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？？在选择物品的时候，对每种物品i只有两种选择，即装入背包或不... 查看详情

01背包+完全背包+多重背包+单调队列(代码片段)

01背包代码：逆序更新intn,m,f[105][N],dp[N];voidfun1()for(inti=1;i<=n;i++)//物品ifor(intj=1;j<=m;j++)//容量jif(j<w[i])f[i][j]=f[i-1][j];elsef[i][j]=max(f[i-1] 查看详情

01背包与完全背包

01背包有一个体积为V的背包，有n个物品，每个物品都有体积vi和价值wi，在背包体积范围内，求能桌下的最大价值。这个问题中每个物品只能用一次。设dp[i][j]表示用前i个物品装体积为j的背包。那么第i个物品要么装要么不装：1... 查看详情

背包问题(01背包）(代码片段)

--------开始--------      每次用到背包问题就忘，今天特意把背包问题写下来，本篇只写01背包问题，至于其它的背包问题以后会陆续出现，大多数背包问题都是以01背包为原型来演变过来的，所以先介绍经典... 查看详情

01背包基础

TheaspiringRoytheRobberhasseenalotofAmericanmovies,andknowsthatthebadguysusuallygetscaughtintheend,oftenbecausetheybecometoogreedy.Hehasdecidedtoworkinthelucrativebusinessofbankrobberyonlyforashortwhi 查看详情

01背包问题和完全背包问题(代码片段)

...coder上面的题目中看到的这个问题，总结一下。先看01背包问题。01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的... 查看详情

01完全多重背包模板

背包问题：背包总容量为W，有n件重量为weight[i],权值为value[i]的物品1、01背包：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。1voidZeroOnePack(intweight,intvalue)2{3for(intw=W;w>=weight;w--)4dp[w]=max(dp[w-weight]+value,... 查看详情