http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=114&problem=1406&mosmsg=Submission+received+with+ID+15392606
给我们两个物品的费用,和一个背包的容量
要求我们使得背包容量浪费最少的情况下,选尽可能多的物品
即要求装满背包的完全背包问题,只要注意初始化就可以了, 将dp[0]置为0, 其他的dp[i]置为-1,表示不合法
然后一个状态必须从一个合法的转移而来,然后在合法的状态转移中选取最大值
dp后,我们逆序枚举容量,找到一个合法的dp状态
那么该dp状态就是浪费容量最少的状态
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/* */
int a[];
int dp[ + ];
int main()
{
int n, i, j;
while (scanf("%d%d%d", &a[], &a[], &n) != EOF)
{
for (i = ; i <= n; ++i)
dp[i] = -;
dp[] = ;
for (i = ; i < ; ++i)
for (j = a[i]; j <= n; ++j)
{
if (dp[j - a[i]] != -)//在合法的状态转移中选取最大值
dp[j] = max(dp[j], dp[j - a[i]] + );
}
for (j = n; j >= ; --j)
if (dp[j] != -)//找个一个合法状态
break;
if (j == n)
printf("%d\n", dp[j]);
else
printf("%d %d\n", dp[j], n - j);
}
return ;
}
uva10465(完全背包,要求装满背包)的更多相关文章
-
题解报告:hdu 1114 Piggy-Bank(完全背包恰好装满)
Problem Description Before ACM can do anything, a budget must be prepared and the necessary financia ...
-
HDU-1114 完全背包+恰好装满问题
B - Piggy-Bank Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Subm ...
-
【DP_背包专题】 背包九讲
这段时间看了<背包九讲>,在HUST VJUDGE上找到了一个题单,挑选了其中16道题集中做了下,选题全部是HDU上的题,大多是简单题.目前做了点小总结,大概提了下每道题的思路重点部分,希 ...
-
01背包模板、全然背包 and 多重背包(模板)
转载请注明出处:http://blog.csdn.net/u012860063 贴一个自觉得解说不错的链接:http://www.cppblog.com/tanky-woo/archive/2010/ ...
-
HDU2159--二维费用背包,三重背包
FATE Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submi ...
-
背包问题(01背包,完全背包,多重背包(朴素算法&;&;二进制优化))
写在前面:我是一只蒟蒻~~~ 今天我们要讲讲动态规划中~~最最最最最~~~~简单~~的背包问题 1. 首先,我们先介绍一下 01背包 大家先看一下这道01背包的问题 题目 有m件物品和一个容量为 ...
-
poj1742(多重背包分解+01背包二进制优化)
Description People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar. ...
-
01背包与完全背包(dp复习)
01背包和完全背包都是dp入门的经典,我的dp学的十分的水,借此更新博客的机会回顾一下 01背包:给定总容量为maxv的背包,有n件物品,第i件物品的的体积为w[i],价值为v[i],问如何选取才能是 ...
-
HDU - 1114 Piggy-Bank 完全背包(背包恰好装满)
Piggy-Bank Before ACM can do anything, a budget must be prepared and the necessary financial support ...
随机推荐
-
酷我音乐API
今天把酷我音乐API分享给大家: 歌曲搜索API:http://search.kuwo.cn/r.s?all={0}&ft=music& itemset=web_2013&cl ...
-
eclipse环境下如何配置tomcat
eclipse环境下如何配置tomcat 很多初学,尤其自学JavaWeb的朋友首次在eclipse下配置tomcat时,总会有种难下手的感觉,在此,通过图文解说的方法,最直观的向大家演示一遍该配置过 ...
-
jQuery中的 return false, e.preventDefault(), e.stopPropagation()的区别
e.stopPropagation()阻止事件冒泡 <html><head> <title></title> <script sr ...
-
Linux系统时间的设置
1. Linux系统时间的设置 在Linux中设置系统时间,可以用date命令: //查看时间[root@node1 ~]# dateTue Feb 25 20:15:18 CST 2014//修改时 ...
-
MP实战系列(七)之集成springboot
springboot是现在比较流行的微服使用的框架,springboot本质上就是将spring+springmvc+mybatis零配置化,基本上springboot的默认配置符合我们的开发.当然有 ...
-
Pangolin中opengl的混合(gl_blend)
Blend 混合是将源色和目标色以某种方式混合生成特效的技术.混合常用来绘制透明或半透明的物体.在混合中起关键作用的α值实际上是将源色和目标色按给定比率进行混合,以达到不同程度的透明.α值为0则完全透 ...
-
《剑指offer》第二十六题(树的子结构)
// 面试题26:树的子结构 // 题目:输入两棵二叉树A和B,判断B是不是A的子结构. #include <iostream> struct BinaryTreeNode { doubl ...
-
js中setAttribute 的兼容性
js中setAttribute 的兼容性class和className兼容方法: object.setAttribute("class","content") ...
-
Prime
#include<iostream>#include<cstdio>#include<cstring>using namespace std; const int ...
-
M4中遇到的问题
MDK5的安装以及破解 这里遇到了一个问题,PDF上并没有扯个界面我就先截了个图然后点安装,后来看来这其中并没有什么问题 在这里就会出现卡死的情况,也就是说并不能从这个界面上下载两个相应的安装包 在M ...