题目链接：https://vjudge.net/contest/103424#problem/K
转载于：https://blog.csdn.net/acm_davidcn/article/details/5549933
题目大意：
给n个物品，和m块钱，输出能够购买最多物品的个数和购买这么多物品的方案数。
解题分析：
背包的一种进化版 , 除了记录最多能买多少个 , 需要记录买这么多个的方法 , 所以要在二维的基础上加多一维 .
状态转移方程如下 : f[i][j][k]=f[i-1][j-t[i]][k-1]+f[i-1][j][k];
( 前 i 个物品在有 j 元的时候买 k 个物品的方法 ,t[i] 为第 i 个物品的价格 )
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int val[], dp[][][]; //dp[i][j][k]表示有k块钱，在前i种物品买j个物品的数量
int main() {
int i, j, k, t, n, m, sign;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (i = ; i <= n; i++)
scanf("%d", &val[i]);
memset(dp, , sizeof(dp));
for (i = ; i <= n; i++)
for (k = ; k <= m; k++)
dp[i][][k] = ; //初始化，一样不买种类是1
for (i = ; i <= n; i++) {
for (j = ; j <= i; j++)
for (k = m; k >= ; k--) {
if (k >= val[i])
dp[i][j][k] += dp[i - ][j - ][k - val[i]] + dp[i - ][j][k]; //加上买和不买的情况
}
}
sign = ;
for (i = n; i >= ; i--) {
if (dp[n][i][m] != ) { //找购买方案数不为0的最大购买数量i
printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dp[n][i][m], i);
sign = ;
break;
}
}
if (!sign)
puts("Sorry, you can't buy anything.");
}
return ;
}
第二种方法，对上述代码进行优化
dp[i][j][0]表示前i个物品有j元时的最多物品数，dp[i][j][1]用来储存方案数
***设当前所选的物品为i
1. 若选了物品i后，能买的件数比不选物品i的件数大，即dp[j - val[i]]>dp[j]
那么更新dp[j]，同时，dp[j][1]的方案数即为dp[j - val[i]][1]
原因是：假设dp[j - val[i]]的方案数为 AB AC 两种，那么在此情况下加个D，为ABD, ACD，仍为两种，所以dp[j] = f[j - val[i]]即可
当然，要注意dp[j - val[i]]为0的情况，因此当它为0时，dp[j] = 1，1即为D
2. 若选了物品i后，能买的件数比不选物品i的件数相同，即dp[j - val[i]] == dp[j]
即原先不选第i个物品，所需要的方案数为dp[j]；而选了物品i的方案数为dp[j - val[i]]。
因此，总的方案数即为dp[j] + dp[j - val[i]]
当然，这里也要注意dp[j - val[i]] = 0的情况，当它为0时，dp[j] += 1，1即为D
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mem(p,k) memset(p,k,sizeof(p))
using namespace std;
int p[], dp[][]; //dp[i][j][0]表示前i个物品，最多有j元，能买多少种物品
int main() { //dp[i][j][1]表示前i个物品，最多有j元，能买最多物品的方案数
int t, cur = ;
cin >> t;
while (t--) {
int m, n;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++)scanf("%d", p + i);
mem(dp, );
for (int i = ; i <= m; i++)dp[i][] = ; //初始化，钱数为j，一个物品都不买的方案数为1（因为此时对应的dp[i][0]=0，表示一个物品都没买）
for (int i = ; i <= n; i++) {
for (int j = m; j >= p[i]; j--) {
if (dp[j][] == dp[j - p[i]][] + ) { //若选了物品i后，能买的件数比不选物品i的件数相同
if (!dp[j - p[i]][])dp[j][] += ;
else
dp[j][] += dp[j - p[i]][];
}
else if(dp[j][]<dp[j - p[i]][] + ) { //若选了物品i后，能买的件数比不选物品i的件数大
dp[j][] = dp[j - p[i]][] + ;
if (!dp[j - p[i]][])dp[j][] = ;
else
dp[j][] = dp[j - p[i]][];
}
}
}
if (dp[m][]) {
printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dp[m][], dp[m][]);
}
else printf("Sorry, you can't buy anything.\n");
}
}
2018-05-21