一道令人抓狂的零一背包变式 -- UVA 12563 Jin Ge Jin Qu hao

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4008

01背包，动态规划。但是01背包变式我第一次做的时候没有想到，结果误入歧途。。后面会贴代码，想直接看题解的不看便是，前面先说题解。

AC代码如下：

```#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>

using namespace std;
const int jingejinqu = 678;
const int MX = 1e5+10;
int dp[MX];
int v[MX];

int main()
{
int T;
scanf("%d", &T);
int k = 0;
while(T--)
{
int summx = 0;
memset(dp, -1, sizeof(dp));
memset(v, 0, sizeof(v));
int n, m;
scanf("%d%d", &n, &m);
dp[0] = 0; //这里注意一下，刚开始从0开始，不然无法进行下去
for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
for(int i = 1; i <= n; ++i)
for(int j = m-1; j >= v[i]; --j)
{
if(dp[j-v[i]] >= 0) dp[j] = max(dp[j], dp[ j-v[i] ]+1);
summx = max(summx, dp[j]);
}
for(int i = m-1; i >= 0; --i)
{
if(dp[i] == summx)
{
printf("Case %d: %d %d\n", ++k, summx+1, i+jingejinqu);
break;
}
}

}
}```
View Code

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

```#include <iostream>
#include <cstdio>
#define ll long long
#include <algorithm>
#include <string.h>

using namespace std;
const int MX = 1e5+10;
const int jinggejinqu = 678;
ll dp[MX];
//ll val[MX];

struct {
ll x;
int flag;
} val[MX];

int main()
{
int T;
scanf("%d", &T);
int k = 0;
while(T--)
{
memset(dp, -1, sizeof(dp));
memset(val, 0, sizeof(val));
int cnt = 1;
int n;
ll m;
scanf("%d%lld", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%lld", &val[i].x);
for(int i = 1; i <= n; ++i)
{
ll x = dp[m];
for(int j = m-1; j >= val[i].x; --j)
{
//dp[j] = max(dp[j], dp[ j-val[i] ]+val[i]);
if(dp[j] < dp[ j-val[i].x ]+val[i].x)
{
dp[j] = dp[ j-val[i].x ]+val[i].x;
//if(j == m) val[i].falg = 1;
}
else dp[j] = dp[j];
}
if(x+val[i].x == dp[m]) val[i].flag = 1;
}

for(int i = 1; i <= n; ++i) if(val[i].flag) cnt++;
ll ans = dp[m]+jinggejinqu;
printf("Case %d: %d %lld\n", ++k, cnt, ans);
}
}```
View Code

```#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>

using namespace std;
const int jingejinqu = 678;
const int MX = 1e7+10;
int dp1[MX], dp2[MX];
int v[MX];

int main()
{
int T;
scanf("%d", &T);
int k = 0;
while(T--)
{
int summx = 0;
memset(dp1, -1, sizeof(dp1));
memset(dp2, 0, sizeof(dp2));
memset(v, 0, sizeof(v));
int n, m;
scanf("%d%d", &n, &m);
dp1[0] = 0;
for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);
for(int i = 1; i <= n; ++i)
for(int j = m-1; j >= v[i]; --j)
{
if(dp1[j-v[i]] >= 0) dp1[j] = max(dp1[j], dp1[ j-v[i] ]+1);
summx = max(summx, dp1[j]);
}
for(int i = 1; i <= n; ++i)
for(int j = m-1; j >= v[i]; --j)
{
dp2[j] = max(dp2[j], dp2[ j-v[i] ]+v[i]);
}
printf("Case %d: %d %d\n", ++k, summx+1, dp2[m-1]+jingejinqu);

}
}```
View Code

这里需要用到一个技巧：对决策进行一定的限定！在计算某个时间最多唱的歌曲时，必须是该时间内恰好唱完这些歌，时间多了不行。即f[j]表示的是在j 的时间恰好用完的情况下最多能唱多少首歌。比如上面的例子只有f[5] 和f[8]等于1，其他的都等于0。这样的话处理时先算出最多唱的歌曲数 num，然后从j = len开始遍历数组f, 第一个等于num的就是在最多歌曲情况下的最长时间。

(0)
(0)

0条