17.4.28 清北第一天水题

多重背包

(backpack.cpp/c/pas)

(1s/256M)

题目描述

提供一个背包，它最多能负载重量为W的物品。

现在给出N种物品：对于第i类物品，一共有Ci件物品；对于每一件物品，重量为Wi，价值为Vi。

找出一种装载方式使得背包中的物品总价值最大。

输入格式(backpack.in)

第一行两个整数N，W，代表物品的种类与背包的总负重。

第2～N+1行，每行三个整数Wi, Vi, Ci，代表第i种物品的重量、价值与数量。

输出格式(backpack.out)

仅一行，一个整数V，代表最大的总价值。

样例输入

3 9

5 8 2

3 6 2

2 1 5

样例输出

数据范围与限制

1<=N<=20, 0<=W<=1000

1<=Wi<=100, 0<=Vi<=100, 0<=Ci<=100

多重背包：

1.动态规划

2.dfs

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 const int N = 25;
 5 int n, t;
 6 int w[N], v[N], c[N];
 7 int ans;
 8 void dfs(int x, int totw, int totv)
 9 {
10     if(x>n)
11     {
12         if(totv > ans) ans = totv;
13         return;
14     }
15     for(int i=0; i<=c[x] && totw + w[x]*i <= t; i++)
16         dfs(x+1, totw + w[x]*i, totv + v[x]*i);
17 }
18 int main()
19 {
20     scanf("%d%d", &n, &t);
21     for(int i=1; i<=n; i++) scanf("%d%d%d", &w[i], &v[i], &c[i]);
22     dfs(1, 0, 0);
23     printf("%d
", ans);
24     return 0;
25 }