HLOJ 1006 0-1背包问题
HDU 2602 Bone Collector类似,但要注意输入顺序,问题规模,最重要的是重量为0的骨头居然也有价值的!
#include<iostream>
using namespace std;
#define N 401
#define M 1501
int f[N][M]; //下标从1开始用
//n种物品,各种物品的容量、价值分别在w、v数组中;c为背包容量
//状态:f[i][j],使用前i种物品构成背包容量为j时能获得的最大价值
//转移方程:f[i][j]=max(f[i-1][j], f[i-1][j-w[i]]+v[i]),
//转移方程中,前者表示不用第i种物品,后者表示用第i种物品
//初值:0种物品时任何容量下能获得的最大价值都为0
//结果:f[n][c]
int max(int a, int b)
{
if(a>b)
return a;
else
return b;
}
int dpKnapSack(int n, int w[], int v[], int c)
{
int i,j;
for (j=0; j<=c; j++) f[0][j]=0;
for (i=1; i<=n; i++)
{
//若有0容量但有价值的物品,则j从0开始,如 HDU 2602 Bone Collector
for (j=1; j<=c; j++)
{
if (j<w[i])//当前容量为j时,第i种物品放不下,肯定不用该物品
f[i][j]=f[i-1][j];
else //在用与不用第i种物品中取大者
f[i][j]=max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
}
}
return f[n][c];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("e:\\input.txt","r",stdin);
#endif
int w[N], v[N];
int n, c, i;
while(scanf("%d%d",&n, &c)!=EOF)
{
for(i=1;i<=n;i++) scanf("%d", &w[i]);
for(i=1;i<=n;i++) scanf("%d", &v[i]);
printf("%d\n", dpKnapSack(n, w, v, c));
}
return 0;
}
分享到:
相关推荐
0-1背包问题是一个经典的动态规划问题:有一个背包,最大承重为W,现有n件物品,每件物品的重量为w[i],价值为v[i]。要求在不超过背包承重的情况下,选择一些物品放入背包,使得背包中物品的总价值最大。 动态规划...
0-1背包问题,部分背包问题。分别实现0-1背包的DP算法,部分背包的贪心算法和DP算法。附件中包含所有算法源代码.c文件,修改下文件名直接编译执行即可
背包问题是一个经典的组合优化问题,通常分为0-1背包问题和分数背包问题两种形式。 1. **0-1背包问题**: 在这个问题中,给定一个背包的容量和一组物品,每个物品有自己的重量和价值。目标是决定哪些物品应该放入...
得宝 迪普乐DP-F850 DP-F650 DP-F620 DP-F550 DP-F520 制版印刷一体机 维修手册
DP/AS-interface Link 20E使用入门pdf,西门子DP/AS-interface Link 20E使用入门:本文介绍了DP/AS-interface Link 20E模块配置方法,程序编写,示例解释
背包问题是一个经典的优化问题,通常有两个版本:0-1背包问题和完全背包问题。以下是这两个问题的简要介绍以及解决方法。 0-1背包问题: 在0-1背包问题中,有一个背包和一组物品,每个物品都有自己的重量和价值。...
dfs回溯法解决0-1背包的问题。 对比dp方法,dfs可以减小空间复杂度。
Dahua大华DH-DPB18-AI 快速操作手册.pdf
西门子NET DP/AS-Interface Link 20E手册pdf,西门子NET DP/AS-Interface Link 20E手册
Dahua大华DH-DPB18-AI 使用说明书.pdf
安装很简单,直接添加打印机,然后选择光盘安装,找到驱动程序,找到相关型号,直接一步到底;然后在打印机属性里面修改相关参数,若是网络打印需要设置打印机地址等参数;
GSD EC1-DEB-DPM Elau
适用于RD-EB、RD-ET、RD-EZ、RD-EB-MX、RD-ET-MX、RD-EZ-MX、KRD-EB、KRD-ET、KRD-EZ、KRD-EB-MX、KRD-ET-MX、KRD-EZ-MX 、SRD-R100、Q3-R100、Q3-R101、Q3-R102、DP-R103、DP-R 113、DP-R123、DP-R133、DP-R143、...
STM32cubeMX--STM32F427--dp83848---freeRTOS--LWIP点灯实验例程
A UMAT of hardening DP-Model with closest point projection mehtod return mapping algorithm in ABAQUS Described in Chinese
DP3-PAA DP3-PDA DP3-PDV DP3-PAV ◎ 上下限报警继电器输出 ◎ 红色高亮数码管14.2mmH ◎ 具有报警回差设定功能 ◎ 显示范围±3999(采用3-3/4位A/D芯片) ◎ 工作电源AC 110/220V 50/60Hz
SIRIUS DP / AS-i F-Link[手册]pdf,
动态规划(DP)——背包问题算法详解[背包九讲]
双CPU热煤炉控制程序,313-2DP+343-1CX10.zip西门子PLC编程实例程序源码下载双CPU热煤炉控制程序,313-2DP+343-1CX10.zip西门子PLC编程实例程序源码下载双CPU热煤炉控制程序,313-2DP+343-1CX10.zip西门子PLC编程实例...
PG&PC;通过S7-300的LAN路由到DP访问CU320-2DP-FAQ-Ver201402.pdf