题目链接:Click here~~
题意:
中文题不解释。
解题思路:
由于最后5元钱可以买任何价值的物品,所以为了使余额最少,我们应该用这5元钱买最贵的物品。
于是问题转化成了容量为V-5,除去一个最贵物品的01背包问题。
#include <stdio.h>
#include <string.h>
#define N 1005
#define max(a,b) a > b ? a : b
int V,dp[N];
void Bag_01(int c,int w)
{
for(int i=V-5;i>=c;i--)
dp[i] = max(dp[i],dp[i-c]+w);
}
int main()
{
int n,w[N],mmax,loc;
while(scanf("%d",&n),n)
......
阅读全文