311-完全背包

内存限制:64MB
时间限制:4000ms
Special Judge: No

accepted:5
submit:7

题目描述:

直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO

输入描述:

第一行： N 表示有多少组测试数据（N<7）。

接下来每组测试数据的第一行有两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0<M<=2000，0<V<=50000)

接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0<c<100000，0<w<100000)

输出描述:

对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包，输出NO）

样例输入:

复制

样例输出:

NO

1

分析：
　　1、完全背包问题是指每个元素可以不止选择一次的背包问题
　　2、它要求所组成的结果必须把背包刚刚填满
　　3、完全背包 = 初始化为负数 + 0-1背包（PS：判断状态方程对应dp的取值情况应该从小到大）
　　　　①、即就是for(int i = c; i<= V; ++ i) ...

核心代码：

 while(m --)

 {

     scanf("%d%d", &v, %w);

     for(int i = v; i <= V; ++ i)

         dp[i] = max(dp[i], dp[i-v] + w);

 }

C/C++代码实现（AC）:

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <stack>

 #include <map>

 #include <queue>

 #include <set>

 using namespace std;

 const int MAXN = ;

 const int MAX = 0x3f3f3f3f;

 int main()

 {

     int t, M, V, c, w, dp[MAXN];

     scanf("%d", &t);

     while(t --)

     {

         memset(dp, -MAX, sizeof(dp));

         dp[] = ;

         scanf("%d%d", &M, &V);

         while(M --)

         {

             scanf("%d%d", &c, &w);

             for(int i = c; i <= V; ++ i) // 从最小的面积考虑起走

                 dp[i] = max(dp[i], dp[i-c] + w);

         }

         if(dp[V] < )

             printf("NO\n");

         else

             printf("%d\n", dp[V]);

     }

     return ;

 }

巴特西

nyoj 311-完全背包 (动态规划，完全背包)

311-完全背包

题目描述:

输入描述:

输出描述:

样例输入:

样例输出:

最新文章

热门文章

巴特西

nyoj 311-完全背包 (动态规划， 完全背包)

311-完全背包

题目描述:

输入描述:

输出描述:

样例输入:

样例输出:

最新文章

热门文章

nyoj 311-完全背包 (动态规划，完全背包)