nyoj--311--完全背包

朴灿烈づ我的快乐病毒、 2022-05-26 06:20 128阅读 0赞

## 完全背包 ##

时间限制： 3500 ms  |  内存限制： 65535 KB

难度： 4

描述

直接说题意，完全背包定义有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）

样例输入

2
    1 5
    2 2
    2 5
    2 2
    5 1

样例输出

NO
    1

基础的完全背包，可作为完全背包的模板：

Java Code

<table style="width:100%;font-family:Consolas, 'Courier New';font-size:12px;vertical-align:text-top;line-height:15px;"> 
 <tbody> 
 <tr> 
 <td style="color:#008284;background-color:#e3e3e3;vertical-align:text-top;"> 
 <div style="margin:7px;text-align:right;white-space:nowrap;">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 
 </div></td> 
 <td style="background-color:#008284;padding:1px;"> 
 <div style="border:1px #008284 solid;"></div></td> 
 <td style="background-color:#efefef;width:100%;vertical-align:text-top;color:#000000;"> 
 <div style="margin:7px;">
 #include&nbsp;&lt;math.h&gt; 
 #include&nbsp;&lt;bits/stdc++.h&gt; 
 
 
 int 
 &nbsp;max( 
 int 
 &nbsp;x, 
 int 
 &nbsp;y) { &nbsp;&nbsp;&nbsp;&nbsp; 
 if 
 (x&gt;y) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return 
 &nbsp;x; &nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return 
 &nbsp;y; } 
 int 
 &nbsp;main() { &nbsp;&nbsp; 
 int 
 &nbsp;t; &nbsp;&nbsp; 
 int 
 &nbsp;c[ 
 2005 
 ]; &nbsp;&nbsp; 
 int 
 &nbsp;v[ 
 2005 
 ]; &nbsp;&nbsp; 
 int 
 &nbsp;dp[ 
 50005 
 ]; &nbsp;&nbsp;scanf( 
 "%d" 
 ,&amp;t); &nbsp;&nbsp; 
 int 
 &nbsp;m,v1; &nbsp;&nbsp; 
 while 
 (t--) &nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d&nbsp;%d" 
 ,&amp;m,&amp;v1); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(dp,- 
 100 
 ,sizeof(dp)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[ 
 0 
 ]= 
 0 
 ; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;i= 
 0 
 ;i&lt;m;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d&nbsp;%d" 
 ,&amp;c[i],&amp;v[i]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;i= 
 0 
 ;i&lt;m;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;j=c[i];j&lt;=v1;j++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[j]=max(dp[j],dp[j-c[i]]+v[i]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if 
 (dp[v1]&lt; 
 0 
 ) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "NO\n" 
 ); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n" 
 ,dp[v1]); &nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp; 
 return 
 &nbsp; 
 0 
 ; } 
 </div></td> 
 </tr> 
 </tbody> 
</table>