首页 > 代码库 > hdu--1114--完全背包
hdu--1114--完全背包
cf分要高涨了。。。
这题 就是个裸体啊 只要读懂题意 现在还是喜欢多做些英文的题目...
touch me
做这题的时候 突然发现 自己对V的遍历顺序为什么在完全背包是顺序 和在01背包是逆序懂了好多....
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int inf = 0x3f3f3f3f; 6 const int size = 10010; 7 const int num = 520; 8 int dp[size]; 9 int value[num]; 10 int weight[num]; 11 12 int main() 13 { 14 cin.sync_with_stdio(false); 15 int t , n , m , p; 16 while( cin >> t ) 17 { 18 while( t-- ) 19 { 20 cin >> n >> m; 21 n = m-n; 22 cin >> p; 23 fill( dp , dp+size , -inf ); 24 dp[0] = 0; 25 for( int i = 0 ; i<p ; i++ ) 26 { 27 cin >> value[i] >> weight[i]; 28 } 29 for( int i = 0 ; i<p ; i++ ) 30 { 31 for( int j = weight[i] ; j<=n ; j++ ) 32 { 33 if(dp[j]<0) 34 dp[j] = dp[ j-weight[i] ] + value[i]; 35 else 36 { 37 if( dp[ j-weight[i] ] + value[i] > 0 ) 38 dp[j] = min( dp[j] , dp[ j-weight[i] ] + value[i] ); 39 } 40 } 41 } 42 if( dp[n]<0 ) 43 { 44 cout << "This is impossible." << endl; 45 } 46 else 47 { 48 cout << "The minimum amount of money in the piggy-bank is " << dp[n] <<"." << endl; 49 } 50 } 51 } 52 return 0; 53 } 54 55 56 #include <iostream> 57 #include <algorithm> 58 using namespace std; 59 60 const int inf = 0x3f3f3f3f; 61 const int size = 10010; 62 const int num = 520; 63 int dp[size]; 64 int value[num]; 65 int weight[num]; 66 67 int main() 68 { 69 cin.sync_with_stdio(false); 70 int t , n , m , p; 71 while( cin >> t ) 72 { 73 while( t-- ) 74 { 75 cin >> n >> m; 76 n = m-n; 77 cin >> p; 78 fill( dp , dp+size , inf ); 79 dp[0] = 0; 80 for( int i = 0 ; i<p ; i++ ) 81 { 82 cin >> value[i] >> weight[i]; 83 } 84 for( int i = 0 ; i<p ; i++ ) 85 { 86 for( int j = weight[i] ; j<=n ; j++ ) 87 { 88 dp[j] = min( dp[j] , dp[j-weight[i]]+value[i] ); 89 } 90 } 91 if( dp[n]==inf ) 92 { 93 cout << "This is impossible." << endl; 94 } 95 else 96 { 97 cout << "The minimum amount of money in the piggy-bank is " << dp[n] <<"." << endl; 98 } 99 }100 }101 return 0;102 }
初始化为-oo的是别人写的 觉得蛮不一样的 因为我写了个初始化+oo的
today:
孤单是一个人的狂欢
狂欢是一群人的孤单
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。