2 qq 33312212 qq_33312212 于 2016.03.15 00:00 提问

poj 1276 背包问题 编译错误 求大神看看 英汉题意如下
poj

Description

A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate @ bills for a requested cash amount. The machine uses exactly N distinct bill denominations, say Dk, k=1,N, and for each denomination Dk the machine has a supply of nk bills. For example,

N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10

means the machine has a supply of 10 bills of @100 each, 4 bills of @50 each, and 5 bills of @10 each.

Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine.

Notes:
@ is the symbol of the currency delivered by the machine. For instance, @ may stand for dollar, euro, pound etc.
Input

The program input is from standard input. Each data set in the input stands for a particular transaction and has the format:

cash N n1 D1 n2 D2 ... nN DN

where 0 <= cash <= 100000 is the amount of cash requested, 0 <=N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k=1,N. White spaces can occur freely between the numbers in the input. The input data are correct.
Output

For each set of data the program prints the result to the standard output on a separate line as shown in the examples below.
Sample Input

735 3 4 125 6 5 3 350
633 4 500 30 6 100 1 5 0 1
735 0
0 3 10 100 10 50 10 10
Sample Output

735
630
0
0
题意:有现今cash,和n种钱币,每种钱币有ni个,价值为di,求各种钱币组成的不超过cash的最大钱数.......

 #include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int imax(int a,int b)
{
    return(a>b?a:b);
}

int main()
{
    int cash;
    int nu;
    while(cin>>cash>>nu)
    {
        vector <int> l;
        l.push_back(0);
        int num=0;
        int n;
        int d;
        int i;
        int j;

        for(i=1;i<nu+1;++i)
        {
            cin>>n>>d;
            num+=n;
            for(j=0;j<n;++j)
            {
                l.push_back(d);
            }
        }
        int f[num+1][cash+1];
        memset(f,0,sizeof(f));
        i=0;
        j=0;

        for(int i=1;i<num+1;++i)
        {
            for(int j=cash;j>=l[i];--j)
            {
                f[i][j]=imax(f[i-1][j-l[i]]+l[i],f[i-1][j]);
            }
        }
        cout<<f[num][cash]<<endl;
    }

    return 0;
}

1个回答

caozhy
caozhy   Ds   Rxr 2016.03.15 06:27
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
poj3624 0-1背包问题
#include #include using namespace std; static const int N = 3403; static const int M = 12881; static int f[N][M]; static int c[N], v[N]; //#define DEBUG int main() { #ifdef DEBUG fstream cin("G:\
poj 1276 多重背包+二进制优化+单调队列优化
Cash Machine Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 27570   Accepted: 9806 Description A Bank plans to install a machine for cash withdrawal. The
poj1276Cash Machine【多重背包模板题】
SubmitStatus Description A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate @ bills for a requested cash amount. The machine uses exactly N disti
poj-1014 多重背包问题
Dividing     题意:有一堆大理石,每个石头的价值在1-6之间,每种价格的石头有多个。现在要求将这堆石头分成两份,使得两份的总价值相同,回答是否存在一种方法将可以实现划分。     这是一道多重背包问题,多重背包问题的做法可以是先将它转化为01背包,再用01背包问题的方法继续求解。转化的思路是,将一个价格下的几件物品,组合成多个价格下个一件物品。比如价格2下原来有7件物品(二进制11
用贪心算法求解背包问题
 1   背包问题的描述:    已知有n种物品和一个可容纳M重量的背包,每种物品i的重量为 。假定将物品i的一部分 放入背包就会得到 的效益,这里, , 。显然,由于背包容量是M,因此,要求所有选中要装入背包的物品总重量不得超过M.。如果这n件物品的总重量不超过M,则把所有物品装入背包自然获得最大效益。现需解决的问题是,这些物品重量的和大于M,该如何装包。2 用贪心策略求解背包问题
poj 2763 Housewife Wind 【树链剖分维护树上权值和】
题目:poj 2763 Housewife Wind 题意:给一个数,边之间有权值,然后两种操作,第一种:求任意两点的权值和,第二,修改树上两点的权值。 分析:很基础的一个树链剖分维护树上权值和,第二道树链剖分题目,也错了好几次。而且这个题目卡vector。有点坑。 AC代码: #include #include #include #include usin
NYOJ - 311 - 完全背包(背包问题)
Problem Description 直接说题意,完全背包定义有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。本题要求是背包恰好装满背包时,求出最大价值总和是多少。如果不能恰好装满背包,输出NO Input第一行: N 表示有多少组测试数据(N Output对应每组测试数据输
poj1144-tarjan求割点
何为割点?也就是题目中的关键点。在一个无向图中,去掉一个点,这个无向图会变成多个子图,那么这个点就叫做割点 同理,割边也是如此,如果去掉一条边,能让无向图变成多个子图,那么这条边叫做割边,所谓的桥。   那么tarjan是如何求的割点的呢? 如果u为割点,当且仅当满足下面的1/2 1、如果u为树根,那么u必须有多于1棵子树 2、如果u不为树根,那么(u,v)为树枝边,当Low[v]>=
用贪心法求解背包问题
贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。 应用:1:该问题可以通过“局部寻优”逐步过渡到“整体最优”,这是贪心选择性质与“动态规划”的主要差别。 2:最优子结构性质:某个问题的整体最优解包含了“子”问题的最优解。 完整的代码如下: [cpp] view plaincopyprint? #include "iostream"   usi
poj2392 多重背包问题
http://poj.org/problem?id=2392 Description The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 <= K <= 400) diff