首页 > 代码库 > hdu--2546--dp<01背包>
hdu--2546--dp<01背包>
距离上一篇 又过去2天了=-=
我发现 我最近开始忘记写 题目链接了 算了 以后 先写链接 省得忘记 touch me
------------
这题 就是个01背包 只是多了一些 限制条件 但读题一定要注意啊..
我刚开始 没读清 一直WA...
当你的金额少于5元时 是不能购买任何东西的 卧槽....
我没仔细看它 ...
当你留意到它以后 只要多个判断条件就好了 然后因为只要有5元 就可以任意购买多少钱的物品 那肯定是去买 最贵的那就可以 在背包dp[x]的时候 将x设为m-5 因为5块钱已经被我们拿去买最贵的物品了
so 就这样..
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int size = 1010; 7 int arr[size]; 8 int dp[size]; 9 10 void zeroOne( int n , int m )11 {12 for( int i = 0 ; i<n ; i++ )13 {14 for( int j = m ; j>=arr[i] ; j-- )15 {16 dp[j] = max( dp[j] , dp[ j-arr[i] ] +arr[i] );17 }18 }19 }20 21 int main()22 {23 int n , m , money , sum;24 while( cin >> n && n )25 {26 memset( dp , 0 , sizeof(dp) );27 for( int i = 0 ; i<n ; i++ )28 {29 cin >> arr[i]; 30 }31 cin >> m;32 money = m;33 if( m<5 )34 {35 cout << m << endl;36 }37 else38 {39 sort( arr , arr+n );40 zeroOne(n-1,m-5);41 cout << m-dp[m-5]-arr[n-1]<<endl;42 }43 }44 return 0;45 }
today:
十二年 一个轮回 一部电影-----少年时代
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。