程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 562 Dividing coins (01背包基礎)

UVA 562 Dividing coins (01背包基礎)

編輯:C++入門知識

UVA 562 Dividing coins (01背包基礎)


 

代碼:

 

/*
* Problem: UVA No.562
* Running time: 0MS
* Complier: C++
* Author: ACM_herongwei
* Create Time: 11:12 2015/9/9 星期三
* zeroonebags  
* 將金幣總價值的一半作為背包容量,然後zeronebags
*/
#include 
#include 
#include 
#include 
#define CLR(c,v) (memset(c,v,sizeof(c)))
using namespace std;

template 
inline _T Max(_T a,_T b)
{
    return (a>b)?(a):(b);
}
template 
inline _T Maxx(_T a,_T b,_T c)
{
    return (a>Max(b,c))?(a):(Max(b,c));
}
const int N  =  1e5 + 10;

int dp[N];
int value[N];

int main()
{
    int Ncase;
    scanf(%d,&Ncase);
    while(Ncase--)
    {
        CLR(dp,0);
        int sum_cost=0, n_bags;
        scanf(%d,&n_bags);
        for(int i=0; i=value[i]; --j)
            {
                if(dp[j]<=dp[j-value[i]]+value[i])
                {
                    dp[j]=dp[j-value[i]]+value[i];
                }
            }
        }
        printf(%d
,sum_cost-2*dp[mid_cost]);
    }
    return 0;
}
/*
sample input
3
3
2 3 5
4
1 2 4 6
4
1 4 5 6
sample ouput
0
1
2
*/


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved