/* 背包問題精選 */
最近在跟着WUYIQI大神練習dp和背包，這周是背包專題，有興趣的童鞋可以點進去看看，WU神說這周的題量很“和諧”╮(╯-╰)╭18道 。。。
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=42402#overview
不管怎樣，還是很感謝WU神為我們找來這麼好的題目，給我們帶來這樣的機會一起練題，學習，謝啦!!☆⌒(*＾-゜)v
怒刷了兩個半天加一個中午，18道也隻刷掉13道，覺得剩下的不太好做了，還是先總結一下，整理整理吧~ o(*￣▽￣*)ブ
A：POJ 3624
最為基礎的01背包，和撿骨頭一樣的難度。不再細說，沒學過01背包的，個人建議還是盡快去看看《背包九講》吧~
直接上代碼：
/*基礎01背包 POJ 3624*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<utility>
#include<iostream>
using namespace std;
#define maxn 3402+5
int n,m;
class charm{
public: int w,d;
}a[maxn];
int dp[12880+100];
int main(){
while(cin>>n>>m){
memset(dp,0,sizeof(dp));
for (int i = 0; i < n; i++)
{
cin>>a[i].w>>a[i].d;
}
for (int i = 0; i < n; i++)
{
for (int j = m; j >= a[i].w; j--)//注意01背包的循環順序
{
dp[j] = max(dp[j],dp[j-a[i].w]+a[i].d);//轉移方程
}
}
printf("%d\n",dp[m]);
}
return 0;
}
B：HDU 2546
應該是高端的飯卡問題。。
題意：購買物品是要確定自己的卡餘額大于等于5，而且一旦大于等于5，就可以買任何價錢的物品（及時購買後餘額為負），問經過合理的購買後能使卡内餘額最小是多少？
思路：跟普通的01背包很相像，可是出現了一個條件：大于等于5塊，可以買到任何價錢的物品。于是想到的思路是用五塊錢（如果有5塊錢）把最貴的物品（不用考慮最貴的商品是否大于5塊錢，因為後來還要減掉）給買了，剩下的用01背包跑一遍，最後結果就是原先的錢數 - 減去5塊剩下的錢能夠買到的最多錢數 - 最貴的物品。
說不明白的看代碼吧：
/*貪心+01背包 HDU 2546*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 1000+5
int n,m;
int a[maxn];
int dp[1000+100];
int main(){
while(cin>>n,n){
memset(dp,0,sizeof(dp));
for (int i = 0; i < n; i++)
{
cin>>a[i];
}
cin>>m;
if(m<5)cout<<m<<endl;
else{
sort(a,a+n);
m -= 5;
for (int i = 0; i < n-1; i++)//用m-5的錢 對前n-1個物品做背包
{
for (int j = m; j >= a[i]; j--)
{
dp[j] = max(dp[j], dp[j-a[i]]+a[i]);
}
}
//printf("%d\n",dp[5]);
printf("%d\n",m+5-dp[m]-a[n-1]);
}
}
return 0;
}
C：UVA 624
題意：你有n分鐘的錄音帶，有m種音樂（隻選一次），分别有其播放的時間， 問怎樣選取音樂，能把錄音帶最大程度的利用上（可能好多詞都翻譯錯了，不過題意差不多。。。）
思路：用m種音樂 背包 可得不超過n的最長總音樂時間。那麼怎樣記錄路徑（具體選了哪幾種音樂）呢？多用一個二維數組p[i][j]記錄在第i首歌，錄音帶還剩j時，是否選擇了這首歌。1表示選擇，0表示未選。具體轉移如下：
01背包轉移方程：dp[i][j] = max(dp[i-1][j],dp[i-1][j-ci]+vi);
那麼如果dp[i][j] == dp[i-1][j] -> 未在第i次選擇的時候選擇第j個。是以p[i][j] = 0;
如果dp[i][j] == dp[i-1][j-ci]+v[i] -> 在第i次選擇的時候選擇了第j個。是以p[i][j] = 1;
然後倒着推，就可以得到一種最佳方案選擇的序列。（本題是special judge）
代碼：
/* 01背包 + 記錄路徑 UVA 624*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 100000+5
int n,m;
int a[25];
int dp[maxn];
bool p[25][maxn];
int stack[25],top;
int main(){
while(scanf("%d %d",&n,&m)!= EOF){
memset(dp,0,sizeof(dp));
memset(p,0,sizeof(p));
for (int i = 1; i <= m; i++)
scanf("%d",&a[i]);
for (int i = 1; i <= m; i++)
{
for (int j = n; j >= a[i]; j--)
{
if(dp[j] <= dp[j-a[i]]+a[i]){//判斷過程
dp[j] = dp[j-a[i]]+a[i];
p[i][j] = 1;
}else{
p[i][j] = 0;
}
}
}
int i = m,v = n;
top = 0;
while(i > 0){//用棧存起來，就可以倒序輸出
if(p[i][v] == 1){
stack[top++] = i;
v -= a[i];
}
i--;
}
while(top>0){
printf("%d ",a[stack[--top]]);
}
printf("sum:%d\n",dp[n]);
}
return 0;
}
D：POJ 2184
考驗思路的一道題（不是自己想出來的，╮(╯▽╰)╭）。
題意：給你n頭奶牛，每頭奶牛有兩個價值，一個TS，一個TF（可正可負），讓你選擇奶牛，當選擇的奶牛的TS，TF之和分别都非負時，TS+TF的最大值。
思路：往01背包上靠，可是這每個物品竟然有兩個價值，難道是二維費用背包，可是又沒有确定下來的背包的容量。糾結糾結又糾結之後，隊友傳來消息：能不能用其中一個價值當做物品花費，另一個價值當做真正的價值，這樣做01背包，把背包容量不定，更新所有的0-100*2000，最後輸出最大的那個結果。
整理起來就是用TS做物品花費，TF做物品價值，做01背包。但是要注意有負數的存在，如果用一維數組做背包，一定要注意第二重循環的順序（因為背包的結果是用前一個狀态轉移來的，更新目前一層的資料時不能更改上一層的資料）。如果是二維數組，就不用糾結循環的順序，不過要更新小于目前物品花費的資料。
代碼：
/* 變形的01背包 POJ 2184*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 2005
#define INF 99999999
#define LL long long
int dp[maxn*100];
int s[105],f[105];//以s為體積，f為價值，做01背包
int main(){
int n,i,j;
while(scanf("%d",&n)!=EOF){
for (i = 1; i <= n; i++)
{
scanf("%d %d",&s[i],&f[i]);
}
for (i = 0; i <= 200000; i++)
{
dp[i] = -INF;
}
dp[100000] = 0;
for (i = 1; i <= n; i++)
{
if(s[i] > 0){//TS正負的時候會有不同的循環順序。
for (j = 200000; j >= s[i]; j--)//一維時要注意循環順序
dp[j] = max(dp[j],dp[j-s[i]] + f[i]);
}else{
if(f[i]<=0)continue;
for (j = 0; j <= 200000+s[i]; j++)//
dp[j] = max(dp[j],dp[j-s[i]] + f[i]);
}
}
int ans = 0;
for (i = 100000; i <= 200000; i++)
{
if(dp[i]>=0)ans = max(ans,dp[i]+i-100000);
}
printf("%d\n",ans);
}
return 0;
}
E：HDU 2639
撿骨頭2
題意：給你n個骨頭的重量和對應骨頭的價值，一個m重量的背包，求第k大的能裝取的骨頭價值。
思路：把問題從求最大的變成求第k大，是以不能隻用一維的dp[j]表示最大值了，用dp[j][k]表示在用j的容量能得到的第k大價值。更新的時候就用O(2*k)的方法更新就可以了。
注意：第k大的定義，是把不同方案得到的相同價值當做一個結果，還是不同方案的結果不同。本題“NOTICE that,we considerate two ways that get the same value of bones are the same.”表明了是第一種。
代碼：
/* 01背包的第k優方案 HDU 2639*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 1000+5
int n,m,k;
int dp[maxn][65];
int c[105],v[105];
void Insert(int r[],int x){
int i;
for (i = 0; i < 2*k; i++) if(r[i] == x)return;
if(x > r[2*k-1])r[2*k-1] = x;
else return ;
for (i = 2*k - 2; i >= 0; i--)
{
if(r[i] < x) r[i+1] = r[i];
else{
r[i+1] = x;break;
}
}
if(i == -1)r[0] = x;
}
int main(){
int t,i,j,a,b;
scanf("%d",&t);
while(t--){
memset(dp,0,sizeof(dp));
scanf("%d %d %d",&n,&m,&k);
for(i = 0;i<n;i++) scanf("%d",&v[i]);
for(i = 0;i<n;i++) scanf("%d",&c[i]);
for (i = 0; i < n; i++)
for (j = m; j >= c[i]; j--)
for (int p = 0; p < k; p++)
{
a = dp[j][p];
Insert(dp[j],a);
a = dp[j-c[i]][p] + v[i];
Insert(dp[j],a);
}
printf("%d\n",dp[m][k-1]);
}
return 0;
}
F：POJ 2923
在WU神的提點下，1A了，o(*￣▽￣*)ゞ
題意：給n（n<=10）個家具的體積，給你兩輛車，有各自的最大容量a,b. 問最少多少趟能夠将這些家具從一個地方移到另一個地方。
思路：由于 n很小，是以想到用狀态壓縮（自己也想到了，沒敢寫╮(╯▽╰)╭，後來咬牙寫了，也就A掉了o(*￣▽￣*)o ）先預處理把兩輛車可以一趟運送的物品狀态。
然後把每個狀态當做物品，做背包就行啦，注意這個背包的物品 之間可能有重疊，是以要另開一個數組s，用來存放上次的狀态，判斷一下前後兩個狀态是否有重疊（s[j-c[i]]&State[i] ?= 0)
代碼：
/* 狀态壓縮 + 背包 */
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int State[2500],c[2500],f[15],n,a,b,ind;
int dp[1005],s[2500];
bool judge(int s,int sum){//01背包判斷 兩車能否裝下
memset(dp,0,sizeof(dp));
for (int i = 0; i < n; i++)
{
if((1<<i) & s){
for (int j = a; j >= f[i]; j--)
{
dp[j] = max(dp[j],dp[j-f[i]]+f[i]);
}
}
}
if(sum-dp[a] > b)return 0;
return 1;
}
void init(){//預處理
ind = 0;
int sum = 0,j;
for (int i = 1; i < (1<<n); i++)
{
sum = 0;j = 0;
while(j < n){
if((1<<j) & i)sum += f[j];
j++;
}
if(sum > a+b)continue;
if(judge(i,sum)){c[ind] = sum;State[ind++] = i;}
}
}
int main(){
int t;scanf("%d",&t);
int cas = 1;
while(t--){
scanf("%d%d%d",&n,&a,&b);
int sum = 0;
for (int i = 0; i < n; i++){
scanf("%d",&f[i]);
sum += f[i];
}
init();
for (int i = 0; i < 1005; i++)
{
dp[i] = 0x3f3f3f3f;
}
memset(s,0,sizeof(s));
dp[0] = 0;
for (int i = 0; i < ind; i++)
{
for (int j = sum; j >= c[i]; j--)
{
if((s[j-c[i]] & State[i]) == 0){//判斷狀态是否有重疊
if(dp[j] > dp[j-c[i]]+1){
dp[j] = dp[j-c[i]] + 1;
s[j] = s[j-c[i]] | State[i];
}
}
}
}
printf("Scenario #%d:\n",cas++);
printf("%d\n\n",dp[sum]);
}
return 0;
}
G：HDU 3466
題意：還是買東西，n個物品，m塊錢，n個物品的價錢p和價值v。不過有所不同的是 每個物品還有一個 預備價錢q>=p，意思是要買這一件物品，隻有你手裡的錢數大于q了，才可以買這個物品。
思路：下意識覺得好簡單啊。。可事實總是打擊人，隻改了背包的第二重循環之後，發現連第二個測試用例都過不了（輸出9）。但是把第二組用例的物品輸入順序變一下，就能得到正确結果。這就讓人費解了啊，，，為啥啊。。。仔細和隊友讨論了之後，發現對于前兩個物品5,10,5和3,5,6。
如果程式隻改了這一段：
for (int i = 0; i < N; i++)
{
for (int j = M; j >= a[i].q/*把a[i].p改掉*/; j--)
{
dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v);
}
}
先處理第一個物品5,10,5，我手裡的錢是10,10>=10了，是以我可以買這件物品，就把dp[10]更新為了5；
再處理第二件物品3,5,6,時 j從10減到5的過程中，隻能得到dp[10] = 6>5，更新dp[10]=6.
但是事實呢，是這樣的：我手裡有10塊錢，達到了第一件物品的預備價格，買到第一件物品，花去5塊，還剩10-5=5塊，得到了5的價值
然後5塊錢也達到了第二件物品的預備價格，買到第二件物品，花去5塊，手裡5-5沒錢了，可是可以得到5+6=11的價值。
可是為何dp轉移的時候，做不到這一點呢？？？
因為第一次隻更新了dp[10]，然而第二次想到dp[10]的時候，必須保證 j-a[i].p >=10 是以j要大于等于13，才能重新更新到。（可以嘗試一下，程式按上面的改，把錢數改成13，隻用前兩個物品，就可以得到11的結果。）
再考慮：怎樣可以避免出現前面更新的時候更新不全？？？
想最基礎的01背包，不在乎物品的輸入順序，這個多了一個預備價格，考慮是不是跟物品做背包的順序有關。。。（好像有點結果論的意思，我也說不太明白╮(￣▽￣")╭ ）。
因為要想先更新第1件物品，再想更新到第二件物品時，需要的背包容量是10+3=13，第一件的預備價格+第二件的真實價格。
如果把順序互換，要更新全，就需要5+5=10，第二件的預備價格+第一件的真實價格。
是以想到 把原先的物品x,y 按 前一件的預備價格 + 後一件真實價格排序，然後再做正常的背包o(*￣▽￣*)ゞ
代碼：
/* 變形01背包 結果與物品順序有關 HDU 3466 */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 2005
#define INF 99999999
#define LL long long
int dp[5050];
int N,M;
struct node{
int p,q,v;
}a[550];
int cmp(node x,node y){
return (x.q+y.p) < (y.q+x.p);//重點啊。。
}
int main(){
while(scanf("%d%d",&N,&M)!=EOF){
memset(dp,0,sizeof(dp));
for (int i = 0; i < N; i++)
scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);
sort(a,a+N,cmp);
for (int i = 0; i < N; i++)
{
for (int j = M; j >= a[i].q/*把a[i].p改掉*/; j--)
{
dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v);
}
}
printf("%d\n",dp[M]);
}
return 0;
}
H： HDU 2126 題意：給n個紀念品（每個紀念品隻能買一次），給m元錢，問最多能買多少個紀念品，而且有幾種選擇方式買到最多的紀念品數。 分析：最多買幾個，就把物品價格看做花費，價值是1，01背包做。求最優方案的個數，可以再開一個數組g[i][j]; 當dp[i-1][j] < dp[i-1][j-a[i]]+1 ,就是買了這個物品比沒買的價值多。假如已經買了兩個，方案是AB,AC兩種，如果多買一個物品D，那麼ABD,ACD還是兩種方案，g[i][j]=g[i-1][j-a[i]]; 需要注意的是，如果之前沒有選，那麼選上目前的物品，就把g[i][j-a[i]]就等于1。 當dp[i-1][j] == dp[i-1][j-a[i]]+1，就是買了這個物品比沒買的價值一樣。那麼就有兩種選擇，g[i][j] = g[i-1][j]+g[i-1][j-a[i]]。當然注意如果之前沒有選，那麼g[i-1][j-a[i]]就等于1。 看代碼：
/* 求最優方案的個數（二維） HDU 2126 */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 550
#define INF 99999999
#define LL long long
//求最優方案的個數
int dp[35][maxn];//dp[i][j] i個物品，花j元，能得到dp個物品。
int g[35][maxn];
int a[maxn]={0};//花費為a，價值是1
int n,m;
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
//for(int i = 0;i<505;i++) g[0][i] = 1;
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; i++)
scanf("%d",&a[i]);
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < a[i]; j++)
{
dp[i][j] = dp[i-1][j];
g[i][j] = g[i-1][j];
}
for (int j = a[i]; j <= m; j++)
{
dp[i][j] = max (dp[i-1][j],dp[i-1][j-a[i]]+1);
if(dp[i-1][j] < dp[i-1][j-a[i]]+1 ){
if(g[i-1][j-a[i]] == 0)g[i][j] = 1;
else g[i][j] = g[i-1][j-a[i]];
}
else if(dp[i-1][j] == dp[i-1][j-a[i]]+1 ){
if(g[i-1][j-a[i]] == 0)g[i][j] = g[i-1][j]+1;
else g[i][j] = g[i-1][j]+g[i-1][j-a[i]];
}
else g[i][j] = g[i-1][j];
}
}
if(dp[n][m] == 0)printf("Sorry, you can't buy anything.\n");
else
printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",g[n][m],dp[n][m]);
}
return 0;
}
/* 求最優方案的個數（一維） */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 550
#define INF 99999999
#define LL long long
//求最優方案的個數
int dp[maxn];//dp[i][j] i個物品，花j元，能得到dp個物品。
int g[maxn];
int a[maxn]={0};//花費為a，價值是1
int n,m;
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; i++)
scanf("%d",&a[i]);
for (int i = 1; i <= n; i++)
for (int j = m; j >= a[i]; j--)
{
if(dp[j] < dp[j-a[i]]+1 ){
dp[j] = dp[j-a[i]]+1;
if(g[j-a[i]] == 0)g[j] = 1;
else g[j] = g[j-a[i]];
}
else if(dp[j] == dp[j-a[i]]+1 ){
if(g[j-a[i]] == 0)g[j] = g[j]+1;
else g[j] = g[j]+g[j-a[i]];
}
}
if(dp[m] == 0)printf("Sorry, you can't buy anything.\n");
else
printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",g[m],dp[m]);
}
return 0;
}
I： HDU 4281 不會做。。
J： UVA 674 題意：給你n元錢，五種硬币，問最多有幾種方式來change。 思路：直接背包就行了。 代碼：
/* UVA 674 */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 6050
#define INF 99999999
#define LL long long
#define mod 100000000000000000
LL dp[7500];
int a[6] = {0,1,5,10,25,50};
int n;
int main(){
memset(dp,0,sizeof(dp));
dp[0] = 1;
for (int i = 1; i <= 5; i++)
for (int j = a[i]; j <= 7489; j++)
dp[j] += dp[j-a[i]];
while(scanf("%d",&n)!=EOF){
printf("%lld\n",dp[n]);
}
return 0;
}
K： UVA 147 題意：和上一題幾乎一模一樣。。 注意：化小數為整數，輸出形式。 代碼： //二維
/* UVA 147 */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 6050
#define INF 99999999
#define LL long long
#define mod 100000000000000000
LL dp[12][maxn];
int x,y;
int n;
int a[12] = {0,1,2,4,10,20,40,100,200,400,1000,2000};//a[i]*5c
int main(){
while(scanf("%d.%d",&x,&y)!=EOF){
if(x==0 && y==0)break;
n = x*20 + y/5;
memset(dp,0,sizeof(dp));
for(int i = 0;i<11;i++)dp[i][0] = 1;
for (int i = 1; i <= 11; i++)
{
for (int j = 0; j < a[i]; j++)
{
dp[i][j] = dp[i-1][j];
}
for (int j = a[i]; j <= n; j++)
{
dp[i][j] = dp[i-1][j] + dp[i][j-a[i]];
}
}
printf("%3d.%02d%17lld\n",x,y,dp[11][n]);
}
return 0;
}
//一維
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 6050
#define INF 99999999
#define LL long long
#define mod 100000000000000000
LL dp[maxn];
int x,y;
int n;
int a[12] = {0,1,2,4,10,20,40,100,200,400,1000,2000};//a[i]*5c
int main(){
memset(dp,0,sizeof(dp));
dp[0] = 1;
for (int i = 1; i <= 11; i++)
{
for (int j = a[i]; j <= 6000; j++)
{
dp[j] += dp[j-a[i]];
}
}
while(scanf("%d.%d",&x,&y)!=EOF){
if(x==0 && y==0)break;
n = x*20 + y/5;
printf("%3d.%02d%17lld\n",x,y,dp[n]);
}
return 0;
}
L： POJ 3181 題意：和上兩題一樣。 注意：結果會超long long ，用高精度，事實證明隻需要用兩位來存，一個存高位，一個存低位，低位設為17位就夠了。 代碼：
/* POJ 3181 */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 1005
#define INF 99999999
#define LL long long
#define mod 100000000000000000
LL dp[maxn][maxn][2];
int N,K;
int main(){
while(scanf("%d%d",&N,&K)!=EOF){
memset(dp,0,sizeof(dp));
for (int i = 0; i < maxn; i++)
dp[i][0][0] = 1;
for (int i = 1; i <= K; i++)
{
for (int j = 0; j < i; j++){
dp[i][j][0] = dp[i-1][j][0];
dp[i][j][1] = dp[i-1][j][1];
}
for (int j = i; j <= N; j++){
dp[i][j][0] = dp[i-1][j][0] + dp[i][j-i][0];
dp[i][j][1] = dp[i-1][j][1] + dp[i][j-i][1];
dp[i][j][1] += dp[i][j][0]/mod;
dp[i][j][0] %= mod;
}
}
if(dp[K][N][1])printf("%lld%017lld\n",dp[K][N][1],dp[K][N][0]);
else printf("%lld\n",dp[K][N][0]);
}
return 0;
}
M： POJ 1787 多重背包 題意：給你四種硬币，各有ci個，讓你去買價錢是n的coffee，要求用最多的硬币去買，輸出最多用的硬币方案（special judge）。 分析：這次不是01背包了，有物品的個數的限制，就是多重背包，多重背包的常用解決方式就是将其化為01背包。比較好的方法是 用二進制分解。 比如5個物品，可以分成1,2,2，三個01的物品，每個物品隻選一個，可以自由組合成0,1,2,3,4,5的方案，是以二者是等價的，再用01背包的方法處理就簡單多了。 再有就是輸出方案，可以參考C題的處理方法。 代碼：
/* POJ 1787 */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 10005
#define INF 99999999
#define LL long long
//需要裝滿的多重背包+輸出方案
int n,m;
struct node{
int c,v;
}p[200];
int dp[maxn];
bool v[200][maxn];
int q[6]={0,1,5,10,25};
int bin[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
void partition(int x,int j){
int i = 0;
while(x){
if(x >= bin[i]){
p[n].c = q[j]*bin[i];
p[n++].v = bin[i];
x -= bin[i];
i++;
}else{
p[n].c = q[j] * x;
p[n++].v = x;
break;
}
}
}
void binary_partition(int a,int b,int c,int d){
n = 0;
partition(a,1); partition(b,2); partition(c,3); partition(d,4);
}
void ZeroOnePack(){
for (int i = 0; i < maxn; i++) dp[i] = -INF;
memset(v,0,sizeof(v));
dp[0] = 0;
for (int i = 0; i < n; i++)
//for (int j = p[i].c; j <= m; j++)
for(int j = m;j>=p[i].c;j--)
if(dp[j] <= dp[j-p[i].c]+p[i].v){
dp[j] = dp[j-p[i].c]+p[i].v;
v[i][j] = 1;
}
if(dp[m] == -INF){printf("Charlie cannot buy coffee.\n");return ;}
int stack[200],top = 0;
int i = n-1,j = m;
while(i >= 0){
if(v[i][j] == 1){
stack[top++] = i;
j -= p[i].c;
}
i--;
}
if(j != 0){printf("Charlie cannot buy coffee.\n");return ;}
int a=0,b=0,c=0,d=0,tmp,tt;
while(top>0){
tmp = stack[--top];
tt = p[tmp].c/p[tmp].v;
if(tt == 1)a += p[tmp].v;
else if(tt == 5)b+= p[tmp].v;
else if(tt == 10)c+= p[tmp].v;
else if(tt == 25)d+= p[tmp].v;
}
printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",a,b,c,d);
}
int main(){
int a,b,c,d;
while(~scanf("%d%d%d%d%d",&m,&a,&b,&c,&d)){
if((m|a|b|c|d) == 0)break;
if(m > (a+b*5+c*10+d*25)){printf("Charlie cannot buy coffee.\n");continue;}
binary_partition(a,b,c,d);
#if 0
printf("%d\n",n);
for (int i = 0; i < n; i++)
printf("%d %d\n",p[i].c,p[i].v);
#endif
ZeroOnePack();
}
//system("pause");
return 0;
}
N： POJ 3260 不會做啊。。
O： POJ 2063 題意：給你n元錢，和kinds種債券，買每個債券，每年有分紅，問你year年後 最多本息加一起 有多少錢。 分析：不斷的做01背包就行了。 注意： The value of a bond is always a multiple of $1 000. 可以把錢數除以1000，減少記憶體。The interest of a bond is never more than 10% of its value. 可以控制最大錢數。 代碼：
/* POJ 2063 */
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define maxn 10005
#define INF 99999999
#define LL long long
int c[15],v[15];
int dp[100000];// 1.1^40 = 45.26
int main(){
int t,n,n1,year,kinds,now;
scanf("%d",&t);
while(t--){
now = 0;
scanf("%d %d",&n,&year);
n1 = n/1000;
scanf("%d",&kinds);
for (int i = 0; i < kinds; i++)
scanf("%d %d",&c[i],&v[i]);
while(now < year){
memset(dp,0,sizeof(dp));
for (int i = 0; i < kinds; i++)
{
for (int j = c[i]/1000; j <= n1; j++)
{
dp[j] = max(dp[j],dp[j-c[i]/1000]+v[i]);
}
}
n += dp[n1];
n1 = n/1000;
now++;
}
printf("%d\n",n);
}
return 0;
}
好啦，我現在能做的都寫上來啦，有什麼問題可以一起讨論哈Σ(⊙▽⊙"a...
![動态規劃之01背包問題講解[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)