無限物品的背包問題
物品無限的背包問題，有n種物品，每種均有無窮多個，第i種物品的體積為Vi，重量為Wi，選一些物品裝到一個容量為C的背包中，使得背包內物品在總體積不超過C的前提下重量盡量大，1≤n≤1001≤n≤100，1≤Vi≤C≤10000，1≤Wi≤106，
測驗資料：
3 5
1 2
2 3
3 2
answer:10
3 7
2 1
3 2
4 3
answer:5
3 5
3 3
4 2
3 2
answer:3
0
解題思路
dp思維：
每個物品都可以無限使用，且我們不需要考慮能否完全利用背包的容量C，只要所裝物品的重量總和最大即可，由于物品是無限使用的，所以在狀態轉移中我們所需要思考的是此時背包的容量，而不是對于面向物品思考狀態，
狀態轉移方程：
i代表著背包的容積
dp【i】=max（dp【i】，dp【i-v【j】】+w【j】）遞回思維：
相當于一個有向圖的動態規劃，我們對每個重量都探討它接下可裝物品的最大重量，
遞回：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 103
#define M 100003
#define Max(a,b) ((a)>(b)?(a):(b))
//由于物品無限且不需要如硬幣問題一樣必須裝的恰到好處
int d[M],C;
int v[N],w[N];
int dp(int C,int n)
{
int *ans=&d[C],i; //ans改變d【c】改變
if(*ans>0) return *ans;
*ans=0;
for(i=0;i<n;i++)
if(C>=v[i])
*ans=Max(*ans,dp(C-v[i],n)+w[i]);
return *ans;
}
int main()
{
int n,ans,i;
while(~scanf("%d%d",&n,&C))
{
for(i=0;i<n;i++)
scanf("%d%d",&v[i],&w[i]);
memset(d,0,sizeof(int)*M); //初始化
ans=dp(C,n);
printf("ans:%d\n",ans);
}
return 0;
}
遞推：
#include <stdio.h>
#include <stdlib.h>
#define N 103
#define M 100003
#define Max(a,b) ((a)>(b)?(a):(b))
int main()
{
int C,n;
while(~scanf("%d%d",&n,&C))
{
int i,j;
int v[n],w[n];
int dp[M]={0}; //初始化為0
for(i=0;i<n;i++)
scanf("%d%d",&v[i],&w[i]);
for(i=1;i<=C;i++)
for(j=0;j<n;j++)
if(i>=v[j])
dp[i]=Max(dp[i],dp[i-v[j]]+w[j]);
printf("ans:%d\n",dp[C]);
}
return 0;
}
01背包問題
有n種物品，每種均只有1個，第i種物品的體積為Vi，重量為Wi，選一些物品裝到一個容量為CC的背包中，使得背包內物品在總體積不超過C的前提下重量盡量大，1≤n≤100，1≤Vi≤C≤10000，1≤Wi≤106，
測驗資料:
5 6
1 2
2 4
3 4
4 5
5 6
answer:10
解題思路
遞回
由于每個物品只能使用一次，所以我們需要標記，類似于DFS進行標記與恢復標記，再利用圖的思維，對著不同體積，探討它接下來體積所能裝下物品重量的最大值
#include <stdio.h>
#include <stdlib.h>
#define N 103
#define M 100003
#define Max(a,b) ((a)>(b)?(a):(b))
int flag[N]; //物品只能用一次需要標記類似dfs
int n,v[N],w[N];
int dp(int C) //為什么不加入記憶化？由于標記的存在并不適合記憶化.
{
int ans=0,i;
for(i=0;i<n;i++)
if(!flag[i] && C>=v[i])
{
flag[i]=1;
ans=Max(ans,dp(C-v[i])+w[i]);
flag[i]=0; //恢復狀態
}
return ans;
}
int main()
{
int C;
while(~scanf("%d%d",&n,&C))
{
int i;
for(i=0;i<n;i++)
scanf("%d%d",&v[i],&w[i]);
printf("ans:%d\n",dp(C));
}
return 0;
}
遞推
二維打表思維*
這回是由于物品只能思考一個，所以我們所要面對思考的物件是物品，而不是此時背包的容量，為什么不面向背包的容量進行思考呢？當你面向背包進行思考時，你就需要加入一個標記，而既然時遞推，你就無法像上面那樣進行多次嘗試，也就是說是遞推限制了我們面向背包容量的思考，
我們要對每個物品需要考慮：裝或者不裝，那么我們的狀態轉移方程就將由此產生，裝下去大呢還是不裝下去大呢
總結：這是把前i個物品裝入背包中的最大重量和的狀態轉移
狀態轉移方程:
dp【i】【j】=max（dp【i-1】【j】，dp【i-1】【j-v【i】】+w【i】） （i代表物品數，j代表重量）
這里我們用的是自底向上的思維
#include <stdio.h>
#include <stdlib.h>
#define N 103
#define M 100003
#define Max(a,b) ((a)>(b)?(a):(b))
int dp[N][M];
int main()
{
int C,n,i,j,v[N],w[N];
while(~scanf("%d%d",&n,&C))
{
for(i=1;i<=n;i++) //由于要預留dp【0】的位置
scanf("%d%d",&v[i],&w[i]);
for(i=0;i<N;i++)
for(j=0;j<M;j++)
dp[i][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=C;j++)
if(j>=v[i])
dp[i][j]=Max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
else
dp[i][j]=dp[i-1][j];
printf("%d\n",dp[n][C]);
}
return 0;
}
我們發現每次dp只需要用到上一層的陣列那么我們可以對dp陣列進行優化，變成一維，
注意：這里對容量C我們需要自頂向下，不然會出現dp改變了前面的數，dp【j-v【i】】+w【i】中的dp【j-v【i】】用的是改變后的數，不是我們所需要的保存上一層陣列的數，
#include <stdio.h>
#include <stdlib.h>
#define N 103
#define M 100003
#define Max(a,b) ((a)>(b)?(a):(b))
int main()
{
int n,C,i,j;
while(~scanf("%d%d",&n,&C))
{
int dp[M]={0};
int v[N],w[N];
for(i=0;i<n;i++)
scanf("%d%d",&v[i],&w[i]);
for(i=0;i<n;i++)
for(j=C;j>=v[i];j--) //這里要自頂向下不然會出現dp【i】改變了前面的數導致后面的j-v【i】用的是改變后的數導致結果例外
dp[j]=Max(dp[j],dp[j-v[i]]+w[i]);
printf("ans%d\n",dp[C]);
}
return 0;
}
還可再進行一點簡單的優化：
for(i=0;i<n;i++){
scanf("%d%d",&v,&w);
for(j=C;j>=v;j--)
dp[j]=Max(dp[j],dp[j-v]+w);
}
勁歌金曲
(If you smiled when you see the title, this problem is for you _)
For those who don’t know KTV, see: https://en.wikipedia.org/wiki/Karaoke_box
There is one very popular song called Jin Ge Jin Qu(勁歌金曲). It is a mix of 37 songs, and is
extremely long (11 minutes and 18 seconds) — I know that there are Jin Ge Jin Qu II and III, and
some other unofficial versions. But in this problem please forget about them.
Why is it popular? Suppose you have only 15 seconds left (until your time is up), then you should
select another song as soon as possible, because the KTV will not crudely stop a song before it ends
(people will get frustrated if it does so!). If you select a 2-minute song, you actually get 105 extra
seconds! ….and if you select Jin Ge Jin Qu, you’ll get 663 extra seconds!!!
Now that you still have some time, but you’d like to make a plan now. You should stick to the
following rules:
? Don’t sing a song more than once (including Jin Ge Jin Qu).
? For each song of length t, either sing it for exactly t seconds, or don’t sing it at all.
? When a song is finished, always immediately start a new song.
Your goal is simple: sing as many songs as possible, and leave KTV as late as possible (since we
have rule 3, this also maximizes the total lengths of all songs we sing) when there are ties.
Input
The first line contains the number of test cases T (T ≤ 100). Each test case begins with two positive
integers n, t (1 ≤ n ≤ 50, 1 ≤ t ≤ 109
), the number of candidate songs (BESIDES Jin Ge Jin Qu)
and the time left (in seconds). The next line contains n positive integers, the lengths of each song, in
seconds. Each length will be less than 3 minutes — I know that most songs are longer than 3 minutes.
But don’t forget that we could manually “cut” the song after we feel satisfied, before the song ends. So
here “length” actually means “length of the part that we want to sing”.
It is guaranteed that the sum of lengths of all songs (including Jin Ge Jin Qu) will be strictly larger
than t.
Output
For each test case, print the maximum number of songs (including Jin Ge Jin Qu), and the total lengths
of songs that you’ll sing.
Explanation:
In the first example, the best we can do is to sing the third song (80 seconds), then Jin Ge Jin Qu
for another 678 seconds.
In the second example, we sing the first two (30+69=99 seconds). Then we still have one second
left, so we can sing Jin Ge Jin Qu for extra 678 seconds. However, if we sing the first and third song
instead (30+70=100 seconds), the time is already up (since we only have 100 seconds in total), so we
can’t sing Jin Ge Jin Qu anymore!Universidad de Valladolid OJ: 12563 – Jin Ge Jin Qu hao 2/2
Sample Input
2
3 100
60 70 80
3 100
30 69 70
Sample Output
Case 1: 2 758
Case 2: 3 777
題意：
假如你的ktv還有15秒就時間到了，但是當你正在唱一首歌的時候他們并不會把你趕走而是會等該歌曲播完才讓你離開，這時你可以點一首兩分鐘的歌，相當于你多唱了105秒，
假如你正在ktv唱歌，還剩下t秒時間，你決定接下來只唱你最愛的n首歌，在時間結束之前你會再點一首《勁歌金曲》（時長678秒），求出你一共唱了幾首歌和唱了多長時間，
輸入n（n<=50）,t(t<=10^9)和每首歌的長度（保證不超過三分鐘），
解題思路
單純的思考所唱的時間最長，就是一個簡單的01背包問題，邊界有所不同是t-1（留一秒給勁歌金曲），
#include <stdio.h>
#include <stdlib.h>
#define Max(a,b) ((a)>(b)?(a):(b))
int main()
{
int T,i,j;
scanf("%d",&T);
while(T--)
{
int n,t,time[50];
int *dp;
scanf("%d%d",&n,&t);
dp=(int *)calloc(t,sizeof(int)); //初始化為0
for(i=0;i<n;i++)
scanf("%d",&time[i]);
for(i=0;i<n;i++)
for(j=t-1;j>=time[i];j--)
dp[j]=Max(dp[j],dp[j-time[i]]+time[i]);
printf("%d\n",dp[t-1]+678);
}
return 0;
}
那么我們再加入一個歌曲數的觀念，你會發現每次歌曲數增加都伴隨著dp（歌唱時間）的增加，那么我們只要將歌曲數的狀態方程放入回圈中同dp一起增加即可，
#include <stdio.h>
#include <stdlib.h>
#define Max(a,b) ((a)>(b)?(a):(b))
int main()
{
int T,i,j;
scanf("%d",&T);
while(T--)
{
int n,t,time[50];
int *dp,*count;
scanf("%d%d",&n,&t);
dp=(int *)calloc(t,sizeof(int)); //初始化為0
count=(int *)calloc(t,sizeof(int));
for(i=0;i<n;i++)
scanf("%d",&time[i]);
for(i=0;i<n;i++)
for(j=t-1;j>=time[i];j--)
{
count[j]=Max(count[j],count[j-time[i]]+1);
dp[j]=Max(dp[j],dp[j-time[i]]+time[i]);
}
printf("%d %d\n",count[t-1]+1,dp[t-1]+678);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282739.html
標籤：其他