hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活(多重背包+dp)

By | 07月31日
Advertisement

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2191

思路分析:该问题为多重背包问题;假设状态dp[i][v]表示在前i件物品中选择物品放入大小为v的背包的最大的重量,则可以第i件物品可以选择0~n[i]件,所以可以得出状态方程 dp[i][v] = Max{dp[i-1][v – k * c[i]] + k * w[i]}, 0 <= k <= n[i];

代码如下:

import java.util.*;

public class Main {
    static int MAX_N = 100 + 10;
    static int[] c = new int[MAX_N];
    static int[] w = new int[MAX_N];
    static int[] n = new int[MAX_N];
    static int[][] dp = new int[MAX_N][MAX_N];

    public static int Max(int a, int b) {
        return a > b ? a : b;
    }
    public static void main(String[] args) {
        int case_times;
        Scanner in = new Scanner(System.in);

        case_times = in.nextInt();
        while (case_times-- != 0) {
            int V, M;

            V = in.nextInt();
            M = in.nextInt();
            for (int i = 1; i <= M; ++ i) {
                c[i] = in.nextInt();
                w[i] = in.nextInt();
                n[i] = in.nextInt();
            }
            for (int i = 0; i < MAX_N; ++ i)
                for (int j = 0; j < MAX_N; ++ j)
                    dp[i][j] = 0;
            for (int i = 1; i <= M; ++ i) {
                for (int v = 0; v <= V; ++ v) {
                    for (int k = 0; k <= n[i]; ++ k)
                        if (v - k * c[i] >= 0)
                            dp[i][v] = Max(dp[i][v], dp[i-1][v - k * c[i]] + k * w[i]);
                }
            }
            System.out.println(dp[M][V]);
        }
    }
}

Similar Posts:

  • hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活

    多重背包问题,用0-1背包来做.稍后看完<背包问题九讲>后再来做. #include<stdio.h> #define NUM 105 int v[NUM],w[NUM],num[NUM],dp[NUM]; int main() { int cases,n,m,i,j,k; //freopen("C:\Documents and Settings\Administrator\桌面\input.txt","r",stdin); scanf(&q

  • hdu 2191悼念512汶川大地震遇难同胞——珍惜现在,感恩生活(多重背包)

    #include<iostream> #include<cstdio> #include<algorithm> /* 虽然该题不排序也可以过,但是我认为价格和重量最大的先买比较合理 */ #include<cstring> #include<string> using namespace std; #define N 105 int dp[N]; struct Node{ int p,h,c; }num[105]; bool cmp(Node a

  • hdu——2191——悼念512汶川大地震遇难同胞——珍惜现在,感恩生活(多重)

    Problem Description 急!灾区的食物依然短缺! 为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,而市场有m种大米,每种大米都是袋装产品,其价格不等,并且只能整袋购买. 请问:你用有限的资金最多能采购多少公斤粮食呢? 后记: 人生是一个充满了变数的生命过程,天灾.人祸.病痛是我们生命历程中不可预知的威胁. 月有阴晴圆缺,人有旦夕祸福,未来对于我们而言是一个未知数.那么,我们要做的就应该是珍惜现在,感恩生活-- 感谢父母,他们给予我们

  • 杭电 HDU ACM 2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活(多重背包)

    悼念512汶川大地震遇难同胞--珍惜现在,感恩生活 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19574    Accepted Submission(s): 8285 Problem Description 急!灾区的食物依然短缺! 为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,

  • HDU 2191 悼念512汶川大地震遇难同胞 【多重背包】

    悼念512汶川大地震遇难同胞--珍惜现在,感恩生活 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19661    Accepted Submission(s): 8322 Problem Description 急!灾区的食物依然短缺! 为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,

  • hdu acm 2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2191 题目意思:有 资金 n 和 m 种类型的大米,对第 i 种类型的大米,价格.数量.袋数分别是: pi, hi, ci,问最多能采购的大米的重量是多少. 多重背包入门题~~~~~~ 在01 背包中两重循环之间多了一重循环 0 ~ bag[i] :表示第 i 种物品的数量从0~bag[i] 枚举. 1 #include <iostream> 2 #include <cstring>

  • HDU 2188 悼念512汶川大地震遇难同胞——选拔志愿者

    最最最基础巴什博奕 #include<stdio.h> #include<iostream> #include<cstring> #include<cmath> #include<queue> using namespace std; int main() { int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); i

  • HDOJ(HDU) 2186 悼念512汶川大地震遇难同胞——一定要记住我爱你

    Problem Description 当抢救人员发现她的时候,她已经死了,是被垮塌下来的房子压死的,透过那一堆废墟的的间隙可以看到她死亡的姿势,双膝跪着,整个上身向前匍匐着,双手扶着地支撑着身体,有些象古人行跪拜礼,只是身体被压的变形了.救援人员从废墟的空隙伸手进去确认了她已经死亡,又在冲着废墟喊了几声,用撬棍在在砖头上敲了几下,里面没有任何回应. 当人群走到下一个建筑物的时候,救援队长忽然往回跑,边跑变喊"快过来".他又来到她的尸体前,费力的把手伸进女人的身子底下摸索,他摸了几下高

  • hdu 2189 悼念512汶川大地震遇难同胞——来生一起走(完全 背包变形--求方案总数)

    题目分析:先筛选1到150以内的宿舍,放到a[num]中,再用完全背包求方案总数 //************ #include<iostream> #include<cstdio> #include<math.h> #include<algorithm> using namespace std; bool is_prime(int x) { for(int i=2;i<=(int)sqrt(x+0.5);i++) if(x%i==0) return

  • HDU 2188-悼念512汶川大地震遇难同胞――选拔志愿者(巴什博奕)

    悼念512汶川大地震遇难同胞――选拔志愿者 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Practice HDU 2188 Appoint description: System Crawler (2015-03-09) Description 对于四川同胞遭受的灾难,全国人民纷纷伸出援助之手,几乎每个省市都派出了大量的救援人员,这其中包括抢险救灾的武警部队,治疗和防疫的医护

Tags: